[백준] 🥇 20057 마법사 상어와 토네이도

📌 난이도

🥇 Gold 3

📌 문제

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

📌 풀이

이 문제를 처음 보자 든 생각은 N1913 달팽이 문제 였다.
하지만, 그 당시 문제를 풀 때, 정석적인 방법인 중앙에서 퍼져나가는 방법이 아니라, 외각쪽에서부터 타고 들어오는 방식으로 구현해서, 다시 중앙에서 퍼지는 방식으로 구현을 하려고 하니까 너무나도 어려웠다.

처음 1시간동안은 중앙에서 퍼져나가는 방법에 대해서 고민했다.
다음 그림처럼 중앙은 1개부터 시작해서 2, 4, 6, 8...와 같은 방식으로 구현하려고 하였다.

하지만 너무나도 어려워서 구상하는 것을 포기하고 다른 방법을 생각하기 시작했다.
그러다가 되게 복잡한 다른 방법을 떠올렸는데, 바로 다음과 같이 크기가 1부터 시작하여 2그룹마다 1씩 증가하면서, 방향은 한 그룹이 끝나면 바로 바뀌는 그런 방식의 중앙에서 뻗어가는 방법이였다.

이후, 이를 이용하여 토네이도를 이동시키고, 토네이도가 이동하면 모래가 움직일 수 있게, MoveSand 함수를 이용하여, 모래를 이동시켜 주었다.
이때 SLR와 SLC를 이용하여 모래가 움직여야 하는 위치를 구해주었다.
하지만 왼쪽으로 이동은 잘 되었지만, 이를 상하좌우에 맞춰 구현해내기 위해서 다음과 같이 2차원 좌표를 구해서 식을 도출해내었다.

일단 2차원 배열은 x, y를 각각 Row, Col이라 했을 때, 이를 좌표평면으로 치환해서 나태내면 다음과 같은 좌표평면이 나타나게 된다.
처음에 SLR와 SLC은 A점을 기준으로 적었다.
이 문제의 모래를 움직이는 방법은 A를 기준으로 봤을 때, 상하대칭이므로, 돌리는 연산 대신 대칭이동시켜도 똑같이 작동한다.
따라서 D를 구하려면 y축에 점을 대칭이동 시키면 되므로, 즉 row와 col값을 서로 바꿔준다.
C점은 A점을 y축에 대칭이동 시키면 되므로, 즉 col에 -1을 곱해주면 된다.
B점은 D점을 x축에 대칭이동 시키면 되므로, A를 기준으로 row와 col을 바꿔준 후, row에 -1을 더해주면 된다.

이때, 이동시킨 점이 field의 바깥이라면, OutSand값에 나간값을 더해주고, 아니면 필드위의 int Sand에 더해주면 된다.

어제 푼 골드3짜리 파이어볼보다는 쉬운 문제인 것 같았지만, 상하좌우로 돌리는 문제가 나와서 수학적으로 어려운 문제였던 것 같다.

그래도 풀어내니까 뿌듯했다.. 😎

📌 Code

package BOJ.Implements;

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

public class N20057 {
    static int N;
    static int[][] field;
    static int OutSand = 0;
    static final int[] DR = {0, 1, 0, -1};
    static final int[] DC = {-1, 0, 1, 0};
    static final int[] SLR = {-2, -1, -1, -1, 0, 1, 1, 1, 2, 0};
    static final int[] SLC = {0, -1, 0, 1, -2, -1, 0, 1, 0, -1};
    static final int[] SLW = {2, 10, 7, 1, 5, 10, 7, 1, 2};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        field = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                field[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //ShowAll(new int[]{N / 2, N / 2});
        Tornado();
        System.out.println(OutSand);
    }

    static void Tornado() {
        int[] pos = new int[]{N / 2, N / 2};
        int dir = 0;
        OutSand = 0;
        int area = 1;
        boolean flag = true;
        while (true) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < area; j++) {
                    pos = new int[]{pos[0] + DR[dir], pos[1] + DC[dir]};
                    if (pos[0] < 0 || pos[0] >= N || pos[1] < 0 || pos[1] >= N) {
                        return;
                    }
                    MoveSand(pos, dir);
                    //ShowAll(pos);
                }
                dir += 1;
                if (dir > 3) {
                    dir = 0;
                }
            }
            area += 1;
        }
    }

    static void MoveSand(int[] pos, int dir) {
        int adjx = 1;
        if (dir == 1 || dir == 2) {
            adjx = -1;
        }
        int sand = field[pos[0]][pos[1]];
        int remainSand = sand;
        field[pos[0]][pos[1]] = 0;
        for (int i = 0; i < SLW.length; i++) {
            if (dir % 2 == 0) {
                if (pos[0] + SLR[i] < 0 || pos[0] + SLR[i] >= N || pos[1] + SLC[i] * adjx < 0 || pos[1] + SLC[i] * adjx >= N) {
                    OutSand += sand * SLW[i] / 100;
                    remainSand -= sand * SLW[i] / 100;
                    continue;
                }
                field[pos[0] + SLR[i]][pos[1] + SLC[i] * adjx] += sand * SLW[i] / 100;
                remainSand -= sand * SLW[i] / 100;
            } else {
                if (pos[0] + SLC[i] * adjx < 0 || pos[0] + SLC[i] * adjx >= N || pos[1] + SLR[i] < 0 || pos[1] + SLR[i] >= N) {
                    OutSand += sand * SLW[i] / 100;
                    remainSand -= sand * SLW[i] / 100;
                    continue;
                }
                field[pos[0] + SLC[i] * adjx][pos[1] + SLR[i]] += sand * SLW[i] / 100;
                remainSand -= sand * SLW[i] / 100;
            }
        }
        if (dir % 2 == 0) {
            if (pos[0] + SLR[9] < 0 || pos[0] + SLR[9] >= N || pos[1] + SLC[9] * adjx < 0 || pos[1] + SLC[9] * adjx >= N) {
                OutSand += remainSand;
            } else {
                field[pos[0] + SLR[9]][pos[1] + SLC[9] * adjx] += remainSand;
            }
        } else {
            if (pos[0] + SLC[9] < 0 * adjx || pos[0] + SLC[9] * adjx >= N || pos[1] + SLR[9] < 0 || pos[1] + SLR[9] >= N) {
                OutSand += remainSand;
            } else {
                field[pos[0] + SLC[9] * adjx][pos[1] + SLR[9]] += remainSand;
            }
        }
    }

    static void ShowAll(int[] pos) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (pos[0] == i && pos[1] == j) {
                    System.out.print(field[i][j] + ")");
                } else {
                    System.out.print(field[i][j] + " ");
                }
            }
            System.out.println();
        }
        System.out.println("=====================================");
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

📌 추가 예제

[Input]
5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

[Output]
10

[Input]
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0

[Output]
10

[Input]
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 10 0
0 0 0 0 0

[Output]
10

[Input]
5
0 0 0 0 0
0 0 0 0 0
0 0 0 10 0
0 0 0 0 0
0 0 0 0 0

[Output]
10

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁