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

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

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

[ 문제풀이 ]

이번 문제는 세분화할 필요가 없을 정도로 정말 단순하게 구현만 하면 되는 문제이다. 주어진 조건에 따라 토네이도가 사라질 때까지 이동시키며 모래를 이동시키면 된다.

​이번 문제를 좀 쉽게 구현하기 위해 내가 사용한 팁? 을 드리겠다.

​1. 격자 밖으로 이동하는 모래를 저장하기 위해 초기 배열을 N이 아닌, 상하좌우 +2한 N+4로 잡은 후 구현하면 조금 더 쉽게 구현이 가능하다.

2. 위 사진처럼 방향에 따라 주어진 비율이 있는데 1개의 2차원 배열로 한 방향을 구현하여 방향에 따라 복잡하게 구현하는 것보다는 5X5 크기밖에 안되기 때문에 4방향을 모두 미리 구현해 놓는다. 이렇게 하면 방향에 따라 복잡하게 구현할 필요가 없어진다.

​3. 모래를 비율에 따라 퍼뜨릴 때 *, / 연산 순서를 조심해야 한다. y의 값을 100으로 나눈 후 비율을 곱하는 순서와 비율을 곱한 후 100으로 나눈 값이 다르다. 후자의 순서로 해야 올바른 답을 얻을 수 있다.

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

public class Main {

	static int N;
	static int[][] A;
	static int[][] dir = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

	//구현하기 편하게 4방향에 따른 비율을 3차원 배열로 만듬
	static int[][][] ratio = { { {0, 0, 2, 0, 0}, {0, 10, 7, 1, 0}, {5, 0, 0, 0, 0}, {0, 10, 7, 1, 0}, {0, 0, 2, 0, 0} },
			{ {0, 0, 0, 0, 0}, {0, 1, 0, 1, 0}, {2, 7, 0, 7, 2}, {0, 10, 0, 10, 0}, {0, 0, 5, 0, 0} },
			{ {0, 0, 2, 0, 0}, {0, 1, 7, 10, 0}, {0, 0, 0, 0, 5}, {0, 1, 7, 10, 0}, {0, 0, 2, 0, 0} },
			{ {0, 0, 5, 0, 0}, {0, 10, 0, 10, 0}, {2, 7, 0, 7, 2}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0} } };

	static class Tornado {
		int y, x, d, cnt;

		public Tornado(int y, int x, int d, int cnt) {
			this.y = y;
			this.x = x;
			this.d = d;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		//격자의 밖으로 나가는 모래까지 저장하기 위해 상하좌우로 +2만큼 해줌
		A = new int[N + 4][N + 4];
		for (int i = 0; i < N; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; ++j) {
				A[i + 2][j + 2] = Integer.parseInt(st.nextToken());
			}
		}

		Tornado tornado = new Tornado((N + 4) / 2, (N + 4) / 2, 0, 0);
		int len = 1; //토네이도의 현재 방향으로 가야할 길이 (1, 1, 2, 2, 3, 3 ... N-1, N-1)
		int count = 0; //len이 2번 방향이 바뀔때마다 +1되기 때문에 이를 체크하기 위한 변수 
		while (true) {
			if (tornado.y == 2 && tornado.x == 2) break;

			//토네이도 방향으로 한칸 이동
			tornado.cnt++;
			tornado.y += dir[tornado.d][0];
			tornado.x += dir[tornado.d][1];

			int val = A[tornado.y][tornado.x];
			int init = val;
			A[tornado.y][tornado.x] = 0;

			//주어진 방향의 Ratio에 따라 모래를 퍼트림
			for (int i = 0; i < 5; ++i) {
				for (int j = 0; j < 5; ++j) {
					if (ratio[tornado.d][i][j] != 0) {
						//"*, /" 연산 순서 조심, 1.*, 2./ 와 1./, 2.*의 결과값이 다름
						int r = val * ratio[tornado.d][i][j] / 100;
						A[tornado.y + i - 2][tornado.x + j - 2] += r;
						init -= r;
					}
				}
			}

			A[tornado.y + dir[tornado.d][0]][tornado.x + dir[tornado.d][1]] += init;

			//방향과 진행할 길이를 갱신
			if (tornado.cnt == len) {
				count++;
				tornado.cnt = 0;
				tornado.d = (tornado.d + 1) % 4;

				if (count == 2) {
					count = 0;
					len++;
				}
			}
		}
		bw.write(getOutArea() + "\n");
		bw.flush(); br.close(); bw.close();
	}

	public static int getOutArea() {
		int answer = 0;

		for (int j = 0; j < N + 4; ++j) {
			for (int i = 0; i < 2; ++i) {
				answer += A[i][j];
			}
			for (int i = N + 2; i < N + 4; ++i) {
				answer += A[i][j];
			}
		}

		for (int i = 2; i < N + 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				answer += A[i][j];
			}
			for (int j = N + 2; j < N + 4; ++j) {
				answer += A[i][j];
			}
		}

		return answer;
	}
}

​