백준 20057번: 마법사 상어와 토네이도 (Java)

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

20057번: 마법사 상어와 토네이도

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

• 3 ≤ N ≤ 499
• N은 홀수
• 0 ≤ A[r][c] ≤ 1,000
• 가운데 칸에 있는 모래의 양은 0

 

---

 

풀이

1. 토네이도 이동 구현

- 방향을 왼쪽을 0이라 하고, 이후 시계 반대방향으로 돌면서 +1씩 해주자. (이동하는 칸 수, 방향) 쌍으로 이동을 표현하자면, (1, 0) -> (1, 1) -> (2, 2) -> (2, 3) -> (3, 0) -> (3, 1) -> ... -> column이 0이 될 때까지 반복이 된다. 이 로직을 코드로 적당히 옮겨주자.

2. 모래 퍼지기 구현

- 10칸으로 퍼지니까, 방향 0에 대하여 '바뀌는 row 정보'를 저장하는 10칸짜리 int 배열, '바뀌는 col 정보'를 저장하는 10칸 int 배열, '해당 구역으로 퍼지는 모래 비율'을 저장하는 10칸 int 배열을 선언한다. 방향이 바뀌는 건, 적당히 돌려주어 구현한다.

 

코드

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

public class Main {
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {-1, 0, 1, 0};
    static int[] dx = {-1, 0, 1, -1, -2, -1, 0, 1, 2, 1};
    static int[] dy = {0, -1, 0, 1, 0, -1, -2, -1, 0, 1};
    static int[] ratio = {7, 55, 7, 1, 2, 10, 5, 10, 2, 1};
    static int[][] map;
    static int N, cnt, len, curLen;
    static Tornado tornado;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        int before = 0;
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                before += map[i][j];
            }
        }
        tornado = new Tornado((N+1)/2, (N+1)/2, 0);
        cnt = 0;
        len = 1;
        curLen = 0;
        while (true) {
            move();
         	// 벗어나면 break
            if (tornado.c < 1) break;
            spread();
        }
        int after = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                after += map[i][j];
            }
        }
        System.out.println(before - after);
    }

    static class Tornado {
        int r;
        int c; 
        int dir;

        public Tornado(int r, int c, int dir) {
            this.r = r;
            this.c = c;
            this.dir = dir;
        }
    }
	
    // tornado의 이동을 구현한 method
    // len만큼 해당 방향으로 이동하는데
    // curlen == len인데 len만큼 이동한게 처음이면
    // 방향만 바꾸고, 두 번째면 len을 늘려준다.
    static void move() {
        if (curLen == len) {
            curLen = 0;
            tornado.dir = (tornado.dir+1) % 4;
            if (cnt == 0) cnt++;
            else {
                cnt = 0;
                len++;
            }
        }

        tornado.r += dr[tornado.dir];
        tornado.c += dc[tornado.dir];
        curLen++;
    }

	// 모래바람이 퍼지는 method
    static void spread() {
        int total = map[tornado.r][tornado.c];
        map[tornado.r][tornado.c] = 0;
        int[] sand = new int[10];
        int rest = 0;
        for (int i = 0; i < 10; i++) {
            if (i == 1) continue;
            sand[i] = (total * ratio[i]) / 100;
            rest += sand[i];
        }
        sand[1] = total - rest;

        for (int i = 0; i < 10; i++) {
            int nx, ny;
            // 방향따라 모래가 퍼지는 방향을 다르게 구현
            if (tornado.dir == 0) {
                nx = tornado.r + dx[i];
                ny = tornado.c + dy[i];
            } else if (tornado.dir == 1) {
                nx = tornado.r - dy[i];
                ny = tornado.c + dx[i];
            } else if (tornado.dir == 2) {
                nx = tornado.r - dx[i];
                ny = tornado.c - dy[i];
            } else {
                nx = tornado.r + dy[i];
                ny = tornado.c - dx[i];
            }
            if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
            map[nx][ny] += sand[i];
        }
    }
}