[BOJ] 21610 마법사 상어와 비바라기 - Java

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

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

---

1. 문제

NxN 크기의 map이 주어지고 비구름의 시작위치는 (N, 1), (N, 2), (N-1, 1), (N-1, 2)이다.

이 비구름의 이동 정보는 M번 주어지고 방향, 횟수로 주어진다.

방향은 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다.

1. 모든 구름이 d방향으로 s칸 이동

2. 구름에서 비가 내려 map에 +1

3. 대각선 칸에 물이 있으면 물이 있는 칸 수만큼 +

4. 구름 다시 세팅 -> 이전 구름 위치 제외하고 물 양이 2 이상이면 구름

2. 풀이

시뮬레이션 문제이다.

내가 놓친 부분은 2가지였다.

1. 구름 좌표를 저장하는 자료구조로 처음에 리스트를 사용하면서 remove할 때 인덱스 때문에 헷갈렸다.

그래서 결국 큐로 변경하였더니 금방 풀 수 있었다.

2. 비 내리고 비바라기를 시전할 때 동시에 처리하여 대각선 체크 시 잘못된 값으로 체크되었다.

모든 구름 좌표에 +1을 먼저 한 다음, 대각선 체크를 해줘야 하는데

나는 좌표마다 +1 후 대각선 체크를 해줬기 때문에 사실상 대각선 좌표가 0이 아닌데도 0으로 체크하고 더하지 않는 상황이 발생하였다.

 

3. 코드

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

public class 마법사상어와비바라기 {

    static int N, M, map[][], ans;
    static Queue<int[]> cloudQ = new ArrayDeque<> ();
    static List<int[]> lastCloudList;
    static List<int[]> moveInfoList = new ArrayList<> ();

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

    static int[] cy = {-1,-1, 1, 1};
    static int[] cx = {-1, 1, 1,-1};

    public static void main(String[] args) throws Exception {
        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+1][N+1]; // 0 dummy
        for (int i = 1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j<=N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int dir = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            moveInfoList.add(new int[] {dir, cnt});
        }
        // 구름 좌표 저장
        cloudQ.offer(new int[] {N-1,1});
        cloudQ.offer(new int[] {N-1,2});
        cloudQ.offer(new int[] {N,1});
        cloudQ.offer(new int[] {N,2});
        // 입력 끝

        solution();
        System.out.println(ans);
    }

    static void solution() {
        for (int i=0; i<M; i++) {
            move(moveInfoList.get(i)[0]-1, moveInfoList.get(i)[1]);
            rain();
            setCloud();
        }
        for (int i = 1; i<=N; i++) {
            for (int j = 1; j<=N; j++) {
                ans += map[i][j];
            }
        }
    }

    static void move(int dir, int cnt) {
        int len = cloudQ.size();
        for (int i=0; i<len; i++) {
            int[] lastLoc = cloudQ.poll();
            int y = lastLoc[0];
            int x = lastLoc[1];
            int ny = y;
            int nx = x;
            for (int c = 0; c<cnt ;c++) {
                if (ny + dy[dir] <= 0) ny = N;
                else if (ny + dy[dir] > N) ny = 1;
                else ny += dy[dir];

                if (nx + dx[dir] <= 0) nx = N;
                else if (nx + dx[dir] > N) nx = 1;
                else nx += dx[dir];
            }
            cloudQ.offer(new int[] {ny, nx});
        }
    }

    static void rain() {
        // 비
        for (int[] loc : cloudQ) {
            map[loc[0]][loc[1]]++;
        }
        //비바라기
        for (int[] loc : cloudQ) {
            int y = loc[0];
            int x = loc[1];
            int cnt = 0;
            for (int crossD = 0; crossD < 4; crossD++) {
                int ny = y+cy[crossD];
                int nx = x+cx[crossD];
                if (ny<=0 || ny>N || nx<=0 || nx>N) continue;
                if (map[ny][nx] > 0) cnt++;
            }
            map[y][x] += cnt;
        }
    }

    static void setCloud() {
        lastCloudList = new ArrayList<> ();
        while (!cloudQ.isEmpty()) {
            lastCloudList.add(cloudQ.poll());
        }
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                if (map[i][j] >= 2) {
                    if (lastCloudCheck(i, j)) continue;
                    map[i][j] -= 2;
                    cloudQ.offer(new int[] {i, j});
                }
            }
        }
    }

    static boolean lastCloudCheck(int i, int j) {
        for (int[] loc : lastCloudList) {
            if (loc[0] == i && loc[1] == j) {
                return true;
            }
        }
        return false;
    }
}

4. 사담

오랜만에 푸니까 시간이 오래걸렸지만 정말 재밌었다.