[백준 JAVA] 21610 마법사 상어와 비바라기

21610 마법사 상어와 비바라기

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

문제설명

격자 형태의 맵에서 구름이 이동하고, 강수를 생성하는 시뮬레이션을 수행한다.

1. 격자: n x n 크기의 격자 맵이 있으며, 각 셀은 물의 양을 나타낸다.
2. 구름의 초기 위치: 구름은 특정 위치에 초기화된다.
3. 이동 명령: m개의 명령이 주어지며, 각 명령은 방향(d)과 거리(s)를 포함한다. 구름은 주어진 방향으로 이동한다.
4. 강수 생성: 구름이 이동한 후, 해당 위치와 대각선 이웃의 물의 양이 증가한다.
5. 신규 구름 생성: 물의 양이 2 이상인 셀은 물의 양을 2 감소시키고, 그 위치에 새로운 구름이 생성된다.

접근방식

O(m * (c + n^2)) 시간복잡도

• 1. 격자 초기화:
     • O(n^2): 입력으로 주어진 격자를 읽는다. 격자의 크기가 n x n인 모든 셀을 읽어야 한다.
  2. 구름 이동:
     • O(c): 구름의 수가 c라고 할 때, 각 구름의 위치를 업데이트한다. 구름의 위치 업데이트는 상수 시간 O(1)이다.
  3. 강수 효과 적용:
     • O(c): 구름이 위치한 셀의 대각선 이웃을 확인하여 물의 양을 증가한다.
     • 대각선 방향의 수가 4개로 고정되어 있어, 각 구름에 대해 일정한 시간 내에 처리가 가능하다.
  4. 신규 구름 생성:
     • O(n^2): 모든 셀을 확인하여 물의 양이 2 이상인 셀을 찾고, 새로운 구름을 생성한다.
     • 격자 전체를 탐색해야 하므로 O(n^2)이 소요된다.
  각 단계에서의 시간을 합산하면 전체 시간 복잡도는 O(m * (c + n^2))로 나타난다.

문제 조건 분석 과정

 

입력으로 격자 크기 n과 명령 수 m을 읽고, n x n 크기의 격자를 초기화한다.

초기 구름의 위치를 설정한다.

 

• 주어진 m개의 명령을 순차적으로 처리한다.
• 각 명령에 대해 이동 방향과 거리를 읽고, 구름의 위치를 업데이트한다.
• 구름이 새로운 위치에 도착하면 해당 셀의 물의 양을 증가시킨다.

• 강수 효과 적용:
  • 각 구름에 대해 대각선 방향의 셀을 확인하고, 물의 양이 1 이상인 경우 카운트한다.
  • 이 카운트를 현재 구름 위치의 물의 양에 추가한다.
• 신규 구름 생성:
  • 모든 셀을 확인하여 물의 양이 2 이상인 경우, 물의 양을 2 감소시키고 그 위치에 새로운 구름을 추가한다.
  • 모든 셀의 물의 양을 합산하여 결과를 출력한다.

 

전체코드

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

public class Main {
    static int n, m;
    static int[][] map;
    static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    static boolean[][] visit;
    static Queue<Cloud> clouds = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][n];
        visit = 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());
            }
        }

        clouds.add(new Cloud(n - 1, 0));
        clouds.add(new Cloud(n - 1, 1));
        clouds.add(new Cloud(n - 2, 0));
        clouds.add(new Cloud(n - 2, 1));

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken()) - 1;
            int s = Integer.parseInt(st.nextToken());

            step12(d, s);
            stept34();
            step5();
        }

        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);
    }

    private static void step12(int d, int s) {
        for (Cloud cloud : clouds) {
            cloud.x = (n + cloud.x + dx[d] * (s % n)) % n;
            cloud.y = (n + cloud.y + dy[d] * (s % n)) % n;
            map[cloud.x][cloud.y]++;
        }
    }

    private static void stept34() {
        while (!clouds.isEmpty()) {
            Cloud cloud = clouds.poll();
            int cnt = 0;

            visit[cloud.x][cloud.y] = true;
            for (int i = 1; i <= 7; i += 2) {
                int nx = cloud.x + dx[i];
                int ny = cloud.y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (map[nx][ny] >= 1)
                        cnt++;
                }
            }
            map[cloud.x][cloud.y] += cnt;
        }
    }

    private static void step5() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j] && map[i][j] >= 2) {
                    map[i][j] -= 2;
                    clouds.add(new Cloud(i, j));
                }
            }
        }
        visit = new boolean[n][n];
    }

    public static class Cloud {
        int x;
        int y;

        public Cloud(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}