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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class MagicianSharkAndRaining {
    static int[] dr = {0,-1,-1,-1,0,1,1,1};
    static int[] dc = {-1,-1,0,1,1,1,0,-1};
    static int[] cr = {-1,1,1,-1};
    static int[] cc = {-1,-1,1,1};
    static int N,M;
    static int[][] map;
    static int[][] move;
    static Queue<int[]> que;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        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());
            }
        }
        move = new int[M][2];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            move[i][0] = Integer.parseInt(st.nextToken());
            move[i][1] = Integer.parseInt(st.nextToken());
        }
        initCloud();
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sum += map[i][j];
            }
        }
        System.out.println(sum);
    }
    public static void initCloud(){
        que = new LinkedList<>();
        que.add(new int[]{N-1,0});
        que.add(new int[]{N-1,1});
        que.add(new int[]{N-2,0});
        que.add(new int[]{N-2,1});
        magic();
    }
    public static void magic(){
        for (int i = 0; i < M; i++) {
            List<int[]> list = new ArrayList<>(moveCloud(i));//구름 이동
            upWater(list);
            createCloud(list);
        }
    }
    public static List<int[]> moveCloud(int index){
        List<int[]> list = new ArrayList<>();
        int len = que.size();

        for (int i = 0; i < len; i++) {
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            int nrow = crow;
            int ncol = ccol;
            for (int j = 0; j < move[index][1]; j++) {
                nrow = (nrow + dr[move[index][0]-1])%N;
                ncol = (ncol + dc[move[index][0]-1])%N;
                if(nrow<0)
                    nrow = N-1;
                if(ncol<0)
                    ncol = N-1;
            }
            map[nrow][ncol] += 1;
            list.add(new int[]{nrow,ncol});
        }
        return list;
    }
    public static void upWater(List<int[]> list){
        for (int i = 0; i < list.size(); i++) {
            int[] current = list.get(i);
            int crow = current[0];
            int ccol = current[1];
            int count = 0;
            for (int j = 0; j < 4; j++) {
                int nrow = crow + cr[j];
                int ncol = ccol + cc[j];
                if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                    continue;
                if(map[nrow][ncol]>0){
                    count++;
                }
            }
            map[crow][ccol] += count;
        }
    }
    public static void createCloud(List<int[]> list){
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                boolean flag = false;
                for (int k = 0; k < list.size(); k++) {
                    if(i==list.get(k)[0]&&j==list.get(k)[1]) {
                        flag = true;
                        break;
                    }
                }
                if(!flag&&map[i][j]>=2){
                    que.add(new int[]{i,j});
                    map[i][j] -= 2;
                }
            }
        }
    }
}

풀이방법

전체 설계

1.초기구름 생성

반복
2. 구름 이동
3. 물의양 증가
4. 구름제거
5. 물복사
6. 맵 전체 범위 구름 생성
7. 물의 양 감소

8.바구니에 물의 양 합 구하기

코드풀이

1. initcloud를 호출해서 que에 초기구름을 생성해서 넣어준다.

2. 이후 magic함수에서 moveCloud를 호출해서 첫번째 이동을 수행한다.

3. que에서 구름의 좌표를 꺼내서 입력값으로 받은 move정보를 통해 구름을 이동시킨다.
   한칸씩 이동하는데, s(i)만큼 반복해준다.
   좌표가 양수범위 밖으로 나가면 다시 첫번째 좌표로 돌아가고, 음수범위 밖으로 나가면, 마지막 좌표로 돌아간다.
   나머지 연산자 %로 양수범위 처리, 음수일때는 마지막 좌표를 넣어준다.

4. 구름 이동이 끝나면 물의양을 +1 씩 해주고, 구름의 위치를 list에 담아놓는다.

5. list를 upWater()에 넘겨서 물복사 버그를 실행한다.

6. list를 돌면서 대각선 4방향에 물이 있는지를 확인하여 그 수만큼 count를 증가시키고, 해당좌표에 count만큼 더해준다.

7. 이후 magic()에서 createCloud()를 호출해서 맵전체를 돌며 2보다 큰좌표가 있는지 확인한다.

8. 이때 구름 list에서 구름의 좌표가 있는 부분은 체크하지 않는다.

9. 2보다 큰 좌표가 있다면 que에 담고, 2번으로 돌아가서 M번만큼의 반복을 수행한다.

10. 반복이 끝나면 맵을 탐색하며 모든 좌표의 물의 양을 더해준다.

후기

조건이 굉장히 많은 구현 문제였다.
특별하게 어려운 부분은 없었지만, 좀 헤멘 부분은 구름이 범위밖으로 넘어가서 이동하는 부분 처리에서 애를 먹었다.
%연산자만 사용하면 될 줄 알았는데, 음수로 돌아가는 부분을 처리해주는 부분이 생각하기 어려웠다.