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

문제 링크

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

풀이 과정

삼성 SW 역량 테스트 기출이며 시뮬레이션 문제입니다.

α 위치에는 모래량 y의 55%가 더해지는 게 아니라, 모래량 y에서 흩뿌려진 모래 sum을 뺀 나머지가 더해지는 것임을 유의해서 문제를 풀어야 합니다.

토네이도는 위의 규칙처럼 이동합니다. 두 번씩, 같은 횟수만큼 칸을 이동하는 것을 볼 수 있습니다.

static int[][] wind = {
        {-2, -1, -1, -1, 0, 1, 1, 1, 2, 0},
        {0, -1, 0, 1, -2, -1, 0, 1, 0, -1},
        {2, 10, 7, 1, 5, 10, 7, 1, 2}
};

위 코드는 그림에서 볼 수 있듯이, 바람에 흩날려 도착하는 곳의 상대 좌표와 모래 비율을 작성해 둔 배열입니다.

• wind[0]는 위 그림의 0~8번까지 위치의 행 증감량이,
• wind[1]은 기준점으로부터의 열 증감량이,
• wind[2]는 각 지역의 모래 비율이 담겨 있습니다.
• 문제에서 α로 주어진 9번 위치에는 모래 비율이 담겨있지 않습니다.

int x = N / 2, y = N / 2;
int dir = 0;
int maxCnt = 1;
int cnt = 0;

while (true) {
    int nx = x + dx[dir], ny = y + dy[dir];
    cnt++;

    scatter(nx, ny, dir);

    if (x == 0 && y == 1) break;

    map[nx][ny] = 0;
    x = nx;
    y = ny;

    if (cnt == maxCnt) {
        dir = (dir + 1) % 4;
        cnt = 0;

        if (dir == 0 || dir == 2) maxCnt++;
    }
}

위 코드는 정 가운데 토네이도가 시작하는 지점을 좌표 (x, y)로 두고, 토네이도가 끝날 때까지 이동시킵니다.

• 토네이도가 (x, y) 에서 (nx, ny) 로 이동하면, scatter 메소드 를 호출해 모래를 정해진 10군데로 이동시켜 줍니다.
• 현재 위치가 (0, 1)이라 토네이도의 이동이 끝났으면 이동을 멈춥니다.
• 아니라면 현재 좌표에 존재하는 모래를 다 제거하고, 이동 방향을 바꿔줄 때가 됐다면 바꿔줍니다.
• 위 과정을 반복합니다.

static void scatter(int x, int y, int dir) {
    int sum = 0;

    for (int i = 0; i < 10; i++) {
        int[] rotated = new int[]{wind[0][i], wind[1][i]};

        for (int d = 0; d < dir; d++) rotated = rotate(rotated);

        int tx = x + rotated[0];
        int ty = y + rotated[1];

        if (i == ALPHA) {
            if (!inRange(tx, ty)) answer += map[x][y] - sum;
            else map[tx][ty] += map[x][y] - sum;

            continue;
        }

        int scatterd = map[x][y] * wind[2][i] / 100;

        if (scatterd == 0) continue;
        else if (!inRange(tx, ty)) answer += scatterd;
        else map[tx][ty] += scatterd;

        sum += scatterd;
    }
}

scatter 메소드 는 10군데로 모래를 분산해 이동시킵니다. 토네이도의 방향에 따라 10군데의 상대적 위치가 달라지므로, rotate 메소드 호출을 통해 현재 토네이도 방향에 알맞은 상대적 위치를 가져옵니다.

아래 값을 타겟 위치 (tx, ty)가 격자 밖이라면, 변수 answer 에 누적시켜주고, 격자 안이라면 타겟 위치에 누적시켜줍니다.

• 타겟 위치 (tx, ty)가 α가 아니라면, map[x][y]에 존재하는 모래양에 타겟 위치의 비율을 곱한 양.
• 타겟 위치 (tx, ty)가 α라면, 9군데에 분배해주고 남은 모래( map[x][y] - sum ).

static int[] rotate(int[] arr) {
    return new int[]{arr[1] == 0 ? 0 : -arr[1], arr[0]};
}

rotate 메소드 는 상대적인 증감량을 나타내는 좌표 (x, y)를 각각 0번째, 1번째 요소로 갖는 1차원 배열을 입력 받아, 반시계방향으로 $90^\circ$회전시킨 후의 좌표를 리턴하는 작업을 수행합니다.

(x, y)를 반시계 방향으로 $90^\circ$회전시키면,

• y가 0인 경우는 (0, x)로,
• y가 0이 아닌 경우는 (-y, x)로 변경됩니다.

코드

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

public class Main {
    static int N;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
    static int[][] wind = {
            {-2, -1, -1, -1, 0, 1, 1, 1, 2, 0},
            {0, -1, 0, 1, -2, -1, 0, 1, 0, -1},
            {2, 10, 7, 1, 5, 10, 7, 1, 2}
    };
    static final int ALPHA = 9;
    static int answer = 0;

    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());
        map = new int[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());
            }
        }

        int x = N / 2, y = N / 2;
        int dir = 0;
        int maxCnt = 1;
        int cnt = 0;

        while (true) {
            int nx = x + dx[dir], ny = y + dy[dir];
            cnt++;

            scatter(nx, ny, dir);

            if (x == 0 && y == 1) break;

            map[nx][ny] = 0;
            x = nx;
            y = ny;

            if (cnt == maxCnt) {
                dir = (dir + 1) % 4;
                cnt = 0;

                if (dir == 0 || dir == 2) maxCnt++;
            }
        }

        System.out.println(answer);
    }

    static void scatter(int x, int y, int dir) {
        int sum = 0;

        for (int i = 0; i < 10; i++) {
            int[] rotated = new int[]{wind[0][i], wind[1][i]};

            for (int d = 0; d < dir; d++) rotated = rotate(rotated);

            int tx = x + rotated[0];
            int ty = y + rotated[1];

            if (i == ALPHA) {
                if (!inRange(tx, ty)) answer += map[x][y] - sum;
                else map[tx][ty] += map[x][y] - sum;

                continue;
            }

            int scatterd = map[x][y] * wind[2][i] / 100;

            if (scatterd == 0) continue;
            else if (!inRange(tx, ty)) answer += scatterd;
            else map[tx][ty] += scatterd;

            sum += scatterd;
        }
    }

    static int[] rotate(int[] arr) {
        return new int[]{arr[1] == 0 ? 0 : -arr[1], arr[0]};
    }

    static boolean inRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}