백준 - 마법사 상어와 토네이도 (20057)

1. 문제 링크

문제 링크

2. 풀이

역시 단순한 구현 문제입니다.
이런 유형은 테이블을 정의하면 쉽게 해결할 수 있습니다.

1. 테이블 정의

int scatter[4][9][3] = {
	{{-1, 1, 1}, {1, 1, 1}, {-2, 0, 2}, {2, 0, 2}, {0, -2, 5}, {-1, 0, 7}, {1, 0, 7}, {-1, -1, 10}, {1, -1, 10}}, // 서
	{{-1, -1, 1}, {-1, 1, 1}, {0, -2, 2}, {0, 2, 2}, {2, 0, 5}, {0, -1, 7}, {0, 1, 7}, {1, -1, 10}, {1, 1, 10}}, // 남
	{{-1, -1, 1}, {1, -1, 1}, {-2, 0, 2}, {2, 0, 2}, {0, 2, 5}, {-1, 0, 7}, {1, 0, 7}, {-1, 1, 10}, {1, 1, 10}}, // 동
	{{1, -1, 1}, {1, 1, 1}, {0, -2, 2}, {0, 2, 2}, {-2, 0, 5}, {0, -1, 7}, {0, 1, 7}, {-1, -1, 10}, {-1, 1, 10}}  // 북
};

문제에 나온 그림과 똑같이
차례대로 서, 남, 동, 북쪽 방향으로 토네이도가 이동할 때,
흩날려 이동할 상대 좌표와 흩날릴 양의 비율을 정의합니다.

2. 토네이도 이동 구현

토네이도는 안쪽에서부터 방향을 회전하며 이동하는데,
두 번 방향을 회전할 때마다 이동 거리가 한 칸씩 늘어나는 규칙이 있습니다.
이 규칙을 이용해 구현해보겠습니다.

void accAccordingOut(int y, int x, int plus) {
	// 격자 바깥일 때
	if (isOut(y, x)) {
		ans += plus;
	}
	else {
		board[y][x] += plus;
	}
}

while (1) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < len; j++) {
			// y 좌표
			int yy = r + my[d];
			int yx = c + mx[d];

			// y좌표가 격자 바깥 -> 현재 격자 끝일 때
			if (isOut(yy, yx)) break;

			// 좌표 갱신
			r = yy;
			c = yx;

			// y 좌표에 모래가 있을 때
			if (board[r][c] > 0) {
				int sum = 0;

				for (int k = 0; k < 9; k++) {
					int ny = r + scatter[d][k][0];
					int nx = c + scatter[d][k][1];
					int amount = board[r][c] * scatter[d][k][2] / 100; // 흩날릴 양

					accAccordingOut(ny, nx, amount);
					sum += amount;
				}

				// 알파 좌표
				int alphaY = r + my[d];
				int alphaX = c + mx[d];

				accAccordingOut(alphaY, alphaX, board[r][c] - sum);
				board[r][c] = 0;
			}

			if (r == 0 && c == 0) {
				isFinish = 1;
				break;
			}
		}

		if (isFinish) break;

		d = (d + 1) % 4; // 방향 전환
	}

	if (isFinish) break; // (0, 0) 좌표 도달시 종료

	len++;
}

accAccordingOut 함수는 단순히 격자 바깥을 나갔는지 여부에 따라
모래를 정답에 누적시키거나, 격자에 누적시키는 함수입니다.
1에서 정의한 테이블을 이용해 토네이도를 이동시키면서 모래를 이동시키고,
(0, 0)도달시, 루프를 빠져나가면 됩니다.

3. 전체 코드

#define SIZE 500
#include <bits/stdc++.h>

using namespace std;

int n, ans = 0;
int my[4] = { 0, 1, 0, -1 };
int mx[4] = { -1, 0, 1, 0 };
int scatter[4][9][3] = {
	{{-1, 1, 1}, {1, 1, 1}, {-2, 0, 2}, {2, 0, 2}, {0, -2, 5}, {-1, 0, 7}, {1, 0, 7}, {-1, -1, 10}, {1, -1, 10}}, // 서
	{{-1, -1, 1}, {-1, 1, 1}, {0, -2, 2}, {0, 2, 2}, {2, 0, 5}, {0, -1, 7}, {0, 1, 7}, {1, -1, 10}, {1, 1, 10}}, // 남
	{{-1, -1, 1}, {1, -1, 1}, {-2, 0, 2}, {2, 0, 2}, {0, 2, 5}, {-1, 0, 7}, {1, 0, 7}, {-1, 1, 10}, {1, 1, 10}}, // 동
	{{1, -1, 1}, {1, 1, 1}, {0, -2, 2}, {0, 2, 2}, {-2, 0, 5}, {0, -1, 7}, {0, 1, 7}, {-1, -1, 10}, {-1, 1, 10}}  // 북
};
int board[SIZE][SIZE];

bool isOut(int y, int x) {
	return y < 0 || y >= n || x < 0 || x >= n;
}

void accAccordingOut(int y, int x, int plus) {
	// 격자 바깥일 때
	if (isOut(y, x)) {
		ans += plus;
	}
	else {
		board[y][x] += plus;
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	int r = n / 2;
	int c = r;
	int d = 0;
	int len = 1;
	int isFinish = 0;

	while (1) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < len; j++) {
				// y 좌표
				int yy = r + my[d];
				int yx = c + mx[d];

				// y좌표가 격자 바깥 -> 현재 격자 끝일 때
				if (isOut(yy, yx)) break;

				// 좌표 갱신
				r = yy;
				c = yx;

				// y 좌표에 모래가 있을 때
				if (board[r][c] > 0) {
					int sum = 0;

					for (int k = 0; k < 9; k++) {
						int ny = r + scatter[d][k][0];
						int nx = c + scatter[d][k][1];
						int amount = board[r][c] * scatter[d][k][2] / 100; // 흩날릴 양

						accAccordingOut(ny, nx, amount);
						sum += amount;
					}

					// 알파 좌표
					int alphaY = r + my[d];
					int alphaX = c + mx[d];

					accAccordingOut(alphaY, alphaX, board[r][c] - sum);
					board[r][c] = 0;
				}

				if (r == 0 && c == 0) {
					isFinish = 1;
					break;
				}
			}

			if (isFinish) break;

			d = (d + 1) % 4;
		}

		if (isFinish) break;

		len++;
	}

	cout << ans;

	return 0;
}