[BaekJoon] 20057 마법사 상어와 토네이도 (Java)

1.  문제 링크

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

2.  문제

요약

• 마법사 상어가 토네이도를 크기가 N x N인 격자로 나누어진 모래밭에서 연습하려고 합니다.
• (r, c) 위치는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미합니다.
• 토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작됩니다.
• 토네이도는 한 번에 한 칸 이동합니다.
• 토네이도가 한 칸 이동할 때마다 모래는 위 그림과 같이 일정한 비율로 흩날리게 됩니다.
• 토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동합니다.
• 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버립니다.
• α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같습니다.
• 이미 모래가 있는 칸으로 모래가 이동하면, 모래의 양은 더해집니다.
• 위 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동한다면 위의 그림을 해당 방향으로 회전시키면 됩니다.
• 토네이도는 (1, 1)까지 이동한 뒤 소멸하고 모래가 격자 밖으로 이동할 수도 있습니다.
• 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 499보다 작거나 같은 홀수인 격자의 크기 N이 주어지고 두 번째 줄부터 N개의 줄에 0보다 크거나 같고 1,000보다 작거나 같은 격자의 각 칸에 있는 모래가 주어집니다. r번째 줄에서 c번째 주어지는 정수는 A[r][c]입니다.
  • 가운데 칸에 있는 모래의 양은 0입니다.
• 출력: 첫 번째 줄에 격자의 밖으로 나간 모래의 양을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, answer;
    static int[] tornado;
    static int[] direction = {2, 1, 0, 3}; // 0: 우, 1: 하, 2: 좌, 3: 상
    static int[][] movedAmount = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static int[][][] neighbor = {{{-1, 1}, {1, 1}, {-1, 0}, {1, 0}, {-2, 0}, {2, 0}, {-1, -1}, {1, -1}, {0, 2}},
                                    {{1, -1}, {1, 1}, {0, -1}, {0, 1}, {0, -2}, {0, 2}, {-1, -1}, {-1, 1}, {2, 0}},
                                    {{-1, -1}, {1, -1}, {-1, 0}, {1, 0}, {-2, 0}, {2, 0}, {-1, 1}, {1, 1}, {0, -2}},
                                    {{-1, -1}, {-1, 1}, {0, -1}, {0, 1}, {0, -2}, {0, 2}, {1, -1}, {1, 1}, {-2, 0}}};
    static double[] percent = {0.1, 0.1, 0.07, 0.07, 0.02, 0.02, 0.01, 0.01, 0.05};
    static int[][] map;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        map = new int[N][N];
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < N; col++) map[row][col] = scanner.nextInt();
        }
    }

    static void solution() {
        answer = 0;
        tornado = new int[] {N / 2, N / 2};
        int count = 0;
        for(int moveNum = 1; moveNum < N; moveNum++) {
            for(int repeat = 0; repeat < (moveNum == N - 1 ? 3 : 2); repeat++) {
                for(int cont = 0; cont < moveNum; cont++) {
                    int dir = direction[count % 4];
                    int[] movedLoc = new int[] {tornado[0] + movedAmount[dir][0], tornado[1] + movedAmount[dir][1]};
                    move(movedLoc, dir);
                    tornado = movedLoc;
                }
                count++;
            }
        }
        System.out.println(answer);
    }

    static void move(int[] loc, int dir) {
        int sand = map[loc[0]][loc[1]], original = map[loc[0]][loc[1]];
        for(int idx = 0; idx < percent.length; idx++) {
            int[] spreadLoc = new int[] {loc[0] + neighbor[dir][idx][0], loc[1] + neighbor[dir][idx][1]};
            int spreadAmount = (int)Math.floor(original * percent[idx]);
            sand -= spreadAmount;
            if(!isInMap(spreadLoc[0], spreadLoc[1])) {
                answer += spreadAmount;
                continue;
            }
            map[spreadLoc[0]][spreadLoc[1]] += spreadAmount;
        }
        if(isInMap(loc[0] + movedAmount[dir][0], loc[1] + movedAmount[dir][1])) {
            map[loc[0] + movedAmount[dir][0]][loc[1] + movedAmount[dir][1]] += sand;
        } else {
            answer += sand;
        }
        map[loc[0]][loc[1]] = 0;
    }

    static boolean isInMap(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 방향을 오른쪽을 0, 아래쪽으로 1, 왼쪽을 2, 위쪽을 3으로 놓고 시작하였습니다.
• 토네이도는 왼쪽, 아래쪽, 오른쪽, 위쪽 방향으로 한 바퀴를 돌기 때문에 우선 direction이라는 1차원 배열에 해당 순서로 방향값을 채워줍니다.
• movedAmount라는 2차원 배열에는 각 방향에서 x축으로 얼만큼, y축으로 얼만큼 이동하는지 값을 세팅해줍니다.
• neighbor라는 3차원 배열에는 각 방향에서 주변에 일정한 비율로 흩날리게 되는 위치들의 좌표들을 세팅해주고 그 위치들에 맞게 percent라는 1차원 배열에 비율을 세팅해줍니다.
• 위와 같이 경우의 수들을 미리 배열들에 넣어두어 이후에 시뮬레이션을 진행할 때 이 배열들을 이용합니다.
• 토네이도는 규칙을 가지는데,
  • 토네이도가 처음 두 번 움직일 때는 한 칸씩 움직이고, 그 다음 두 번 움직일 때는 두 칸씩 움직이고, 그 다음 두 번을 움직일 때는 세 칸씩 움직여, 즉 두 번의 이동마다 이동 거리가 한 칸씩 늘어납니다.
  • 또한 두 번씩 N - 2번을 움직이고 마지막 N - 1번째 움직임에는 세 번을 움직입니다.

토네이도의 규칙
1. 토네이도는 왼쪽, 아래쪽, 오른쪽, 위쪽 방향 순서로 반복하며 움직입니다.
2. 토네이도는 (왼쪽, 아래쪽), (오른쪽, 위쪽) 쌍을 이뤄 움직인다고 볼 수 있는데, 한 번 쌍이 움직일 때 움직이는 칸 수가 한 칸씩 늘어납니다.

예를 들어, 처음 움직일 때 (왼쪽, 아래쪽)을 움직이는데, 이 때는 각각 한 칸을 움직이고
그 다음 움직일 때는 (오른쪽, 위쪽)을 움직이는데 이 때는 각각 두 칸을 움직입니다.
그 다음 세 번째 움직일 때는 다시 (왼쪽, 아래쪽)을 움직이는 이 때는 각각 세 칸을 움직입니다.

3. 그러나 마지막 움직임 때는 두 개가 쌍을 이루는 것이 아닌 세 개가 쌍을 이뤄 움직입니다.
4. 한 쌍의 움직임을 한 번이라고 봤을 때, 총 움직임은 N - 1번 일어납니다.

   즉, 격자가 5 x 5 크기라면, 총 4번 움직이는데, 움직이는 순서는 (왼쪽, 아래쪽), (오른쪽, 위쪽), (왼쪽, 아래쪽), (오른쪽, 위쪽, 왼쪽) 순서로 움직입니다.
   

• 이러한 토네이도가 움직이는 규칙을 이용하여 총 N - 1번 움직이는데, 만약 N - 1번째 움직임이 아니라면 총 2개의 방향으로, N - 1번째 움직임이라면 총 3개의 방향으로 움직이도록 2중 for문을 작성하고, 한 번의 움직임에 움직이는 칸 수가 한 칸씩 늘어나므로 이를 반영하여 3중 for문을 작성합니다.
• 각 움직임에서 방향은 count라는 변수를 이용하여 구하는데, count를 4로 나눈 나머지에 해당하는 수를 구하고, direction 배열에서 나머지를 index로 하여 그 위치에 있는 방향이 지금 움직이는 방향이 됩니다.
• 각 움직임에서는 neighbor와 percent라는 배열을 이용하여 모래가 흩날리는 주변 위치를 찾아 그에 맞는 비율로 모래가 흩날리도록 하고, 만약 모래가 흩날리는 주변 위치가 격자 바깥이라면 그 모래들의 양을 더해서 밖으로 흩날리는 모래의 양을 찾습니다.
• 만약 일정한 비율로 모래가 흩날리는 위치들로 모래가 흩날린 뒤에 모래가 남아있다면 해당 모래는 α 위치로 옮겨주고 지금 현재 토네이도가 위치한 곳의 모래를 0으로 만들어줍니다.