[BOJ 21610] 마법사 상어와 비바라기 - JAVA, Gold5

https://www.acmicpc.net/problem/21610

21610번: 마법사 상어와 비바라기

사용한 알고리즘 : 구현

 

풀이전략

1. 구름 이동 후 해당 지역 바구니에 물 1 추가

2. 물복사 버그 (비가 내렸던 지역의 대각선 지역 양동이가 0이 아닌 개수만큼 +)

3. 맵에서 비가 내렸던 지역을 제외한 지역들 중 양동이의 물이 2이상인 지역에 구름 생성

4. 모든 지역의 양동이 물 총합 출력

 

1. 구름 이동 후 바구니에 물 1 추가

static int dx[] = {0,-1,-1,-1,0,1,1,1};
static int dy[] = {-1,-1,0,1,1,1,0,-1};

for(Position cloud:cloudList){
    int mx = cloud.row+(dx[direction]*distance);
    int my = cloud.col+(dy[direction]*distance);

    if(mx<0) mx = N+mx;
    else mx%=N;
    if(my<0) my = N+my;
    else my%=N;

    map[mx][my]++;
    isRained[mx][my]=true;
}
cloudList.clear();

cloudsLIst : 구름이 있는 지역 좌표를 가진 ArrayList

direction : ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 방향을 0~7로 나타냄

distance : 거리

 

입력으로 주어진 방향과 거리만큼 구름을 이동시키고, 해당 지역에 비를 내려 양동이에 1을 더함

또 해당 지역을 비가 내렸던 지역으료 표기하고 비 구름들을 없앰

 

2. 물복사 버그(비가 내린 지역의 대각선 지역 양동이가 0이 아닌 개수만큼 +)

static int dx2[] = {-1,-1,1,1};
static int dy2[] = {-1,1,1,-1};

for(int r=0;r<N;++r){
    for(int c=0;c<N;++c){
        if(isRained[r][c]){
            for(int j=0;j<4;++j){
                int mx = r + dx2[j];
                int my = c + dy2[j];

                if(mx<0 || mx>=N || my<0 || my>=N) continue;
                if(map[mx][my]!=0) map[r][c]++;
            }
        }
    }
}

맵의 모든 지역을 순회하며 해당 지역이 비가 내렸던 지역인 경우,

해당 지역의 대각선 방향(↖, ↗, ↘, ↙) 지역의 양동이 물 양이 0이 아니면

그 수 만큼 원래 지역의 양동이에 물을 더해준다.

 

3. 맵에서 비가 내렸던 지역을 제외한 지역들 중 양동이의 물이 2이상인 지역에 구름 생성

for(int row=0;row<N;++row){
    for(int col=0;col<N;++col){
        if(!isRained[row][col] && map[row][col]>=2){
            cloudList.add(new Position(row,col));
            map[row][col]-=2;
        }

    }
}

비가 내리지 않은 지역이면서, 지역 양동이 물 양이 2이상인 경우

해당 지역에 구름을 생성하고(list에 추가) 양동이의 물을 2 제거한다.

 

4. 모든 지역의 양동이 물 총합 출력

static int resultSum(){
    int sum=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            sum+=map[i][j];
        }
    }
    return sum;
}

최종적으로 구해야 할 목표였던 모든 지역의 양동이 물 총합을 반환한다.

 

제출코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N,M;
    static int map[][];
    static class Position{
        int row;
        int col;

        public Position(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static int command[][];

    static int dx[] = {0,-1,-1,-1,0,1,1,1};
    static int dy[] = {-1,-1,0,1,1,1,0,-1};

    static int dx2[] = {-1,-1,1,1};
    static int dy2[] = {-1,1,1,-1};

    static List<Position> cloudList = new ArrayList<>();

    static void func(){

        for(int i=0;i<M;++i){

            int direction = command[i][0];
            int distance = command[i][1]%N;

            boolean isRained[][]= new boolean[N][N];


            for(Position cloud:cloudList){

                int mx = cloud.row+(dx[direction]*distance);
                int my = cloud.col+(dy[direction]*distance);

                if(mx<0) mx = N+mx;
                else mx%=N;
                if(my<0) my = N+my;
                else my%=N;

                map[mx][my]++;
                isRained[mx][my]=true;
            }
            cloudList.clear();

            for(int r=0;r<N;++r){
                for(int c=0;c<N;++c){
                    if(isRained[r][c]){
                        for(int j=0;j<4;++j){
                            int mx = r + dx2[j];
                            int my = c + dy2[j];

                            if(mx<0 || mx>=N || my<0 || my>=N) continue;
                            if(map[mx][my]!=0) map[r][c]++;
                        }
                    }
                }
            }

            for(int row=0;row<N;++row){
                for(int col=0;col<N;++col){
                    if(!isRained[row][col] && map[row][col]>=2){
                        cloudList.add(new Position(row,col));
                        map[row][col]-=2;
                    }

                }
            }
        }
    }

    static int resultSum(){
        int sum=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                sum+=map[i][j];
            }
        }
        return sum;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        command = new int[M][2]; // [x][0] = 방향, [x][1] = 거리

        for(int i=0;i<N;++i){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;++j){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<M;++i){
            st = new StringTokenizer(br.readLine());
            command[i][0]=Integer.parseInt(st.nextToken())-1;
            command[i][1]=Integer.parseInt(st.nextToken());
        }

        cloudList.add(new Position(N-1,0));
        cloudList.add(new Position(N-1,1));
        cloudList.add(new Position(N-2,0));
        cloudList.add(new Position(N-2,1));

        func();

        bw.write(resultSum()+"\n");
        bw.flush();
        bw.close();
    }
}