백준, 마법사 상어와 비바라기(21610, java)

문제 설명

NxN 격차에 바구니가 들어 있고 각 바구니에는 물을 채울 수 있다. 이때 주어진 명령을 순서대로 이동하면서 최종적으로 저장된 물의 양을 구하는 문제이다.

 

일단 비바라기를 시전하면 첫 (N,1), (N,2), (N-1,1), (N-1,2)에 비구름이 생긴다. 그리고 구름이 d 방향으로 s 거리만큼 이동한다. 이때 d 방향은 상하좌우 뿐만 아니라 각 대각선으로 이동할 수 있고 지도는 서로 이어져 있다. 지도가 이어져 있다는 의미는 가장 윗 칸에서 한 칸 더 올라가면 제일 마지막 칸으로 가고 또 마지막 칸에서 한 칸 내려가면 제일 윗 칸이 나온다는 의미이다. 이는 오른쪽과 왼쪽도 동일하다.

 

이동한 후 진행되는 순서는 다음과 같다.

 

1. 이동한 위치에 물이 1씩 증가한다. 그리고 구름이 사라진다.

2. 물이 증가 한 칸들을 기준으로 각 대각선 위치에 물이 있는 칸의 수 만큼 물이 증가한다. 이때 경계를 넘어가지는 않는다.

3. 바구니에 저장된 물의 양이 2이상이면 해당 칸에 구름이 생기고 물의 양이 2만큼 줄어든다. 다만, 구름이 사라졌던 부분에는 새로 구름이 생기지 않는다.

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

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

문제 풀이

문제에서 주어진 대로 풀어주면 된다.

구름의 이동

구름을 주어진 방향과 횟수만큼 이동한다. 이때 조심해야 할 건 바로 경계를 넘어서는 순간이다. 지도는 상하좌우가 이어져 있기에 경계를 넘어서도라도 반대편에 있는 위치로 이동하게 해야 한다.

 

이를 mod로 풀어줄 수도 있지만, 나는 직관적으로 아래처럼 위치를 조정했다.

                if(r < 0){
                    r = n-1;
                }
                if(c < 0){
                    c = n-1;
                }
                if(r >= n){
                    r = 0;
                }
                if(c >= n){
                    c = 0;
                }

아니면 이렇게 mod로 풀어줄 수 있다.

            cloud.x = (N + cloud.x + dx[d] * (s % N)) % N;
            cloud.y = (N + cloud.y + dy[d] * (s % N)) % N;

참고로 나는 이렇게 새로 구한 구름의 위치를 리스트에 set로 변경해 넣어줬다. 그러나 이는 큐나 스택으로도 풀 수 있다.

        //구름을 이동한다. -> map이 연결되어 있음에 주의
        for(int i = 0; i< clouds.size(); i++){
            pair current = clouds.get(i);
            int r = current.r;
            int c = current.c;
            for(int j=0; j<s; j++){
                r += dR[d];
                c += dC[d];
                if(r < 0){
                    r = n-1;
                }
                if(c < 0){
                    c = n-1;
                }
                if(r >= n){
                    r = 0;
                }
                if(c >= n){
                    c = 0;
                }
            }
            clouds.set(i, new pair(r, c));
        }

구름이 이동한 칸에 비가 내려 물의 양이 1 증가한다.

구름들의 위치를 가지고 와서 각 위치에 값을 1 증가시킨다. 그리고 여기서 현재 구름의 위치를 표시해줘야 하는데, 그 이유는 나중에 새로 구름을 만들 때 현재 구름의 위치에는 구름을 만들 수 없기 때문이다.

        //이동한 칸에 비가 내려 물의 양이 1 증가한다.
        for(int i=0; i<clouds.size(); i++){
            pair current = clouds.get(i);
            map[current.r][current.c] += 1;
            currentClouds[current.r][current.c] = true;
        }

물이 1증가한 칸의 대각선을 검사해 물이 들어 있는 칸의 수 만큼 물을 더해준다.

구름이 들어 있는 각 칸의 대각선에 존재하는 칸들 중 물이 들어있는 칸의 수를 구한다. 이때의 대각선은 경계를 넘지 않는다고 했으니, 지도 범위 안에 들어있는지 확인하고 칸에 물이 있으면 수를 증가한다. 모든 대각선을 검사해줬으면 해당 칸에 구한 물을 더해준다.

        //구름이 있는 각 칸의 대각선을 검사해서 물이 있는 칸의 수 만큼 물이 증가한다.
        for(int i=0; i<clouds.size(); i++){
            pair current = clouds.get(i);
            int r = current.r;
            int c = current.c;
            int count = 0;
            for(int j=1; j<8; j+=2){
                int nR = r+ dR[j];
                int nC = c+  dC[j];
                //대각선은 경계를 넘어가지 않는 칸만 검사한다.
                if(nR >= 0 && nR < n && nC >= 0 && nC < n){
                    if(map[nR][nC] != 0){
                        count += 1;
                    }
                }
            }
            map[current.r][current.c] += count;
        }

새 구름 만들기

모든 칸을 돌면서 물의 양이 2보다 크면 새 구름을 만든 후 리스트에 저장해준다. 해당 반복문을 시작하기 전에 리스트에 있는 값들을 전부 지워야 함을 잊지 말자. 또한 만일 현재 구름이 생겼다가 사라진 자리라면 구름을 만들어 주지 않는다. 다만, 다음 실행을 위해서 해당 자리를 false로 원상복구 시켜야 한다. 그리고 구름을 만들어 줬다면 2를 빼주도록 한다.

        clouds.clear();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] >= 2){
                    if(currentClouds[i][j]){
                        currentClouds[i][j] = false;
                        continue;
                    }
                    clouds.add(new pair(i, j));
                    map[i][j] -= 2;
                }

            }
        }

코드

java

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

class pair{
    int r;
    int c;
    pair(int r, int c){
        this.r = r;
        this.c = c;
    }
}

public class Main {

    public static int n, m;

    public static int[] dC = {-1, -1, 0, 1, 1, 1, 0, -1};
    public static int[] dR = {0, -1, -1, -1, 0, 1, 1, 1};
    public static int[][] map;
    public static boolean[][] currentClouds;
    public static ArrayList<pair> clouds;

    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());
        int d, s;
        int answer = 0;

        map = new int[n][n];
        clouds = new ArrayList<>();
        clouds.add(new pair(n-1, 0));
        clouds.add(new pair(n-1, 1));
        clouds.add(new pair(n-2, 0));
        clouds.add(new pair(n-2, 1));

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

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            d = Integer.parseInt(st.nextToken())-1;
            s = Integer.parseInt(st.nextToken());
            move(d, s);
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                answer += map[i][j];
            }
        }

        System.out.println(answer);
    }

    public static void move(int d, int s){

        //구름을 이동한다. -> map이 연결되어 있음에 주의
        for(int i = 0; i< clouds.size(); i++){
            pair current = clouds.get(i);
            int r = current.r;
            int c = current.c;
            for(int j=0; j<s; j++){
                r += dR[d];
                c += dC[d];
                if(r < 0){
                    r = n-1;
                }
                if(c < 0){
                    c = n-1;
                }
                if(r >= n){
                    r = 0;
                }
                if(c >= n){
                    c = 0;
                }
            }
            clouds.set(i, new pair(r, c));
        }

        //이동한 칸에 비가 내려 물의 양이 1 증가한다.
        for(int i=0; i<clouds.size(); i++){
            pair current = clouds.get(i);
            map[current.r][current.c] += 1;
            currentClouds[current.r][current.c] = true;
        }

        //구름이 있는 각 칸의 대각선을 검사해서 물이 있는 칸의 수 만큼 물이 증가한다.
        for(int i=0; i<clouds.size(); i++){
            pair current = clouds.get(i);
            int r = current.r;
            int c = current.c;
            int count = 0;
            for(int j=1; j<8; j+=2){
                int nR = r+ dR[j];
                int nC = c+  dC[j];
                //대각선은 경계를 넘어가지 않는 칸만 검사한다.
                if(nR >= 0 && nR < n && nC >= 0 && nC < n){
                    if(map[nR][nC] != 0){
                        count += 1;
                    }
                }
            }
            map[current.r][current.c] += count;
        }

        clouds.clear();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j] >= 2){
                    if(currentClouds[i][j]){
                        currentClouds[i][j] = false;
                        continue;
                    }
                    clouds.add(new pair(i, j));
                    map[i][j] -= 2;
                }

            }
        }
    }
}