[백준] 21610번 마법사 상어와 비바라기 - Java, 자바

난이도

골드 5

문제

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

풀이

주어진 조건을 차례대로 잘 구현하면 되는 문제.
이 문제에서 어려웠던 점은 구름을 di 방향으로 si 칸 이동하는 부분 로직을 짜는 것이었는데, 이 부분 유의하면서 기억하도록 하자.

1. 큐를 생성해서 구름 위치를 저장한다.

    public static class Cloud {
        int x;
        int y;

        public Cloud(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
...
	static Queue<Cloud> clouds = new LinkedList<>();
...
	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));

2. 다음 로직을 m 만큼 반복한다.

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

step12(d, s)
1) 구름이 di 방향으로 si칸 이동
2) 구름이 있는 칸 물의 양이 1 증가

    private static void step12(int d, int s) {
        // 구름 이동, 구름 칸 물의 양 1 증가
        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]++;
        }

    }

구름 이동 로직 :

• n번 이상 이동할 경우 n으로 나머지 연산한 결과와 동일함으로 s%n
  dx[d]는 si(s%n)만큼 이동 = dx[d]*(s%n)
• 행과 열의 0번째 칸이 n-1번째 칸과 이어져있기 때문에 이 경우를 처리해줘야하는데
  n을 앞에 더해주고 마지막에 n으로 나머지 연산하여 이어져있도록 하였다.

stept34()
3) 구름 제거 -> clouds.poll();
4) 물복사 버그마법 시전(대각선에 물바구니 있으면 그만큼 증가)

    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;

        }

    }

step5()
5) 물의양 2이상인 칸에 구름 생기고 물의 양 2 줄이기 (이때, 3에서 구름 사라진 칸 제외)

    private static void step5() {
        // 물의양 2이상인 모든칸 구름 생기고 물양 2줄어들기 (단, 3에서 구름이 사라진 칸 무시)
        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]; 

    }

3. 모든 바구니에 있는 물의 양의 합을 구한다.

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

코드

package 삼성SW역량테스트기출문제;

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

public class BOJ21610 {
    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) {
        // 구름 이동, 구름 칸 물의 양 1 증가
        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() {
        // 물의양 2이상인 모든칸 구름 생기고 물양 2줄어들기 (단, 3에서 구름이 사라진 칸 무시)
        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;
        }
    }
}