[백준] 21610번: 마법사 상어와 비바라기 (Java)

1. 문제설명

NxN 크기의 격자가 있고, 각 칸에는 바구니가 하나 있다. 이 바구니에 저장할 수 있는 물의 양에는 제한이 없다. A[r][c]는 {r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 범위는 (1, 1) (N, N) 이다. 1번 행과 N번 행을 연결하고, 1번 열과 N번 열을 연결한다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 에 비구름이 생긴다. 구름에 이동을 M번 명령한다. i번째 이동 명령은 방향 $d_i$과 거리 $s_i$로 이루어져 있다. 방향은 인접한 8방향이 있으며, 8개의 정수로 표현한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구한다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

• 시간 제한: 1초
• 메모리 제한: 1024MB

2. 접근 방식

참고: https://velog.io/@kimmjieun/백준-21610번-마법사-상어와-비바라기-Java-자바

• 크기가 [N+1][N+1]인 각 칸의 물의 양을 저장하는 배열을 생성한다.
• 8개의 방향을 의미하는 dx, dy배열을 생성한다. (←, ↖, ↑, ↗, →, ↘, ↓, ↙)
• (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름을 생성한다.
• 비구름을 이동하는 명령을 수행한다.
  1. 모든 구름을 $d_i$ 방향으로 $s_i$ 칸 이동시키고, 구름 칸에 물의 양을 1 증가시킨다.
     • 구름 이동 로직 :
       • n번 이상 이동할 경우 n으로 나머지 연산한 결과와 동일함으로 s%ndx[d]는 si(s%n)만큼 이동 = dx[d]*(s%n)
       • 행과 열의 0번째 칸이 n-1번째 칸과 이어져있기 때문에 이 경우를 처리해줘야하는데n을 앞에 더해주고 마지막에 n으로 나머지 연산하여 이어져있도록 하였다.
  2. 구름을 모두 제거하고, 물복사버그 마법을 시전한다. (대각선 방향에 물바구니 있으면 그만큼 물의 양 증가)
     • 이동과 다르게 경계를 넘어가는 칸은 대각형 방향으로 거리가 1인 칸이 아니다.
  3. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

 

3. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m; // 격자 크기, 이동 명령 수
    static int map[][]; // 물의 양을 저장하는 격자
    static Queue<int[]> cloud; // 구름 칸 저장
    static boolean[][] visited; // 구름 사라진 칸 확인

    // 8가지 방향
    static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};

    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]; // 격자
        visited = new boolean[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());
            }
        }

        // 비구름 생성
        cloud = new LinkedList<>(); // 구름 위치 저장
        cloud.add(new int[]{n-1, 0});
        cloud.add(new int[]{n-1, 1});
        cloud.add(new int[]{n-2, 0});
        cloud.add(new int[]{n-2, 1});

        // m번 이동 수행
        while(m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());

            moveCloud_addWater(d, s); // 구름 이동 & 구름 칸 물의 양 1 증가
            removeCloud_bugWater(); // 구름 제거 & 물복사버그 시전
            addCloud_deWater(); // 구름 생성 & 물의 양 감소시킴
        }

        System.out.println(getWater()); // 모든 칸의 물의 양의 합
    }

    // 구름 이동 & 구름 칸 물의 양 1 증가
    static void moveCloud_addWater(int d, int s) {
        for(int[] c : cloud) {
            // 방향 d로 s칸 이동 (1-based 처리)
            c[0] = (n + c[0] + dx[d] * (s % n)) % n;
            c[1] = (n + c[1] + dy[d] * (s % n)) % n;

            map[c[0]][c[1]]++; // 물의 양 증가
        }
    }

    // 구름 제거 & 물복사버그 시전
    static void removeCloud_bugWater() {
        while(!cloud.isEmpty()) {
            int[] c = cloud.poll();
            visited[c[0]][c[1]] = true; // 구른 사라진 칸 체크

            // 대각선 방향 탐색
            for(int i=1; i<=7; i+=2) {
                int nx = c[0] + dx[i];
                int ny = c[1] + dy[i];
                // 대각선 위치가 격자 범위 내에 있으면
                if(nx>=0 && nx<n && ny>=0 && ny<n) {
                    if(map[nx][ny] >= 1) // 물이 들어있으면
                        map[c[0]][c[1]]++;
                }
            }
        }
    }

    // 구름 생성 & 물의 양 감소시킴
    static void addCloud_deWater() {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                // 구름이 사라진 칸이 아니고 물의 양이 2 이상인 칸
                if(!visited[i][j] && map[i][j] >= 2) {
                    cloud.add(new int[]{i, j}); // 구름 저장
                    map[i][j] -= 2; // 물의 양 2 감소시킴
                }
            }
        }
        visited = new boolean[n][n]; // 구름 사라진 칸 초기화
    }

    // 모든 칸의 물의 양의 합
    static int getWater() {
        int mount = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                mount += map[i][j];
            }
        }
        return mount;
    }
}