마법사 상어와 토네이도 (feat. 백준, 20057번)

마법사 상어와 토네이도
https://www.acmicpc.net/problem/20057

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

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/20057
#include <iostream>
using namespace std;
struct Move {
	int x, y, percent;		// 현재 기준 움직여야할 x, y 좌표 및 이동시켜야할 모래의 퍼센트
};
int N, arr[500][500], dx[4], dy[4], direction, result;
Move calc_sand[4][9];		// 한 방향당 9개의 퍼센트, 방향은 서,남,동,북
inline void init() {
	direction = result = 0;
	// 서, 남, 동, 북 방향
	dx[0] = 0, dx[1] = 1, dx[2] = 0, dx[3] = -1;
	dy[0] = -1, dy[1] = 0, dy[2] = 1, dy[3] = 0;
	// 서, 남, 동, 북 방향 나눠져야할 모래 정보
	// 서쪽
	calc_sand[0][0].x = -1, calc_sand[0][0].y = -1, calc_sand[0][0].percent = 10;
	calc_sand[0][1].x = -1, calc_sand[0][1].y = 0, calc_sand[0][1].percent = 7;
	calc_sand[0][2].x = -1, calc_sand[0][2].y = 1, calc_sand[0][2].percent = 1;
	calc_sand[0][3].x = -2, calc_sand[0][3].y = 0, calc_sand[0][3].percent = 2;
	calc_sand[0][4].x = 1, calc_sand[0][4].y = -1, calc_sand[0][4].percent = 10;
	calc_sand[0][5].x = 1, calc_sand[0][5].y = 0, calc_sand[0][5].percent = 7;
	calc_sand[0][6].x = 1, calc_sand[0][6].y = 1, calc_sand[0][6].percent = 1;
	calc_sand[0][7].x = 2, calc_sand[0][7].y = 0, calc_sand[0][7].percent = 2;
	calc_sand[0][8].x = 0, calc_sand[0][8].y = -2, calc_sand[0][8].percent = 5;
	// 동쪽
	calc_sand[2][0].x = -1, calc_sand[2][0].y = -1, calc_sand[2][0].percent = 1;
	calc_sand[2][1].x = -1, calc_sand[2][1].y = 0, calc_sand[2][1].percent = 7;
	calc_sand[2][2].x = -1, calc_sand[2][2].y = 1, calc_sand[2][2].percent = 10;
	calc_sand[2][3].x = -2, calc_sand[2][3].y = 0, calc_sand[2][3].percent = 2;
	calc_sand[2][4].x = 1, calc_sand[2][4].y = -1, calc_sand[2][4].percent = 1;
	calc_sand[2][5].x = 1, calc_sand[2][5].y = 0, calc_sand[2][5].percent = 7;
	calc_sand[2][6].x = 1, calc_sand[2][6].y = 1, calc_sand[2][6].percent = 10;
	calc_sand[2][7].x = 2, calc_sand[2][7].y = 0, calc_sand[2][7].percent = 2;
	calc_sand[2][8].x = 0, calc_sand[2][8].y = 2, calc_sand[2][8].percent = 5;
	// 남쪽
	calc_sand[1][0].x = -1, calc_sand[1][0].y = -1, calc_sand[1][0].percent = 1;
	calc_sand[1][1].x = -1, calc_sand[1][1].y = 1, calc_sand[1][1].percent = 1;
	calc_sand[1][2].x = 0, calc_sand[1][2].y = -1, calc_sand[1][2].percent = 7;
	calc_sand[1][3].x = 0, calc_sand[1][3].y = 1, calc_sand[1][3].percent = 7;
	calc_sand[1][4].x = 0, calc_sand[1][4].y = -2, calc_sand[1][4].percent = 2;
	calc_sand[1][5].x = 0, calc_sand[1][5].y = 2, calc_sand[1][5].percent = 2;
	calc_sand[1][6].x = 1, calc_sand[1][6].y = -1, calc_sand[1][6].percent = 10;
	calc_sand[1][7].x = 1, calc_sand[1][7].y = 1, calc_sand[1][7].percent = 10;
	calc_sand[1][8].x = 2, calc_sand[1][8].y = 0, calc_sand[1][8].percent = 5;
	// 북쪽
	calc_sand[3][0].x = 1, calc_sand[3][0].y = -1, calc_sand[3][0].percent = 1;
	calc_sand[3][1].x = 1, calc_sand[3][1].y = 1, calc_sand[3][1].percent = 1;
	calc_sand[3][2].x = 0, calc_sand[3][2].y = -1, calc_sand[3][2].percent = 7;
	calc_sand[3][3].x = 0, calc_sand[3][3].y = 1, calc_sand[3][3].percent = 7;
	calc_sand[3][4].x = 0, calc_sand[3][4].y = -2, calc_sand[3][4].percent = 2;
	calc_sand[3][5].x = 0, calc_sand[3][5].y = 2, calc_sand[3][5].percent = 2;
	calc_sand[3][6].x = -1, calc_sand[3][6].y = -1, calc_sand[3][6].percent = 10;
	calc_sand[3][7].x = -1, calc_sand[3][7].y = 1, calc_sand[3][7].percent = 10;
	calc_sand[3][8].x = -2, calc_sand[3][8].y = 0, calc_sand[3][8].percent = 5;
}
inline void spread_sand(const int& x, const int& y, const int sand) {
	auto nx = 0, ny = 0;
	for (int idx = 0, divided_sand; idx < 9; ++idx) {
		divided_sand = (sand * calc_sand[direction][idx].percent) / 100;
		if (divided_sand > 0) {
			nx = x + calc_sand[direction][idx].x, ny = y + calc_sand[direction][idx].y;
			if (1 <= nx && nx <= N && 1 <= ny && ny <= N)		arr[nx][ny] += divided_sand;
			else												result += divided_sand;
			arr[x][y] -= divided_sand;
		}
	}
	nx = x + dx[direction], ny = y + dy[direction];
	if (1 <= nx && nx <= N && 1 <= ny && ny <= N)				arr[nx][ny] += arr[x][y];
	else														result += arr[x][y];
	arr[x][y] = 0;
}
inline void solve(int x, int y) {
	int move_length = 1, idx, m, nx, ny;
	while (true) {
		for (int idx = 0; idx < 2; ++idx) {
			for (m = 0; m < move_length; ++m) {
				nx = x + dx[direction], ny = y + dy[direction], x = nx, y = ny;
				if (arr[x][y] > 0)		spread_sand(x, y, arr[x][y]);
				if (x == 1 && y == 1)		return;
			}
			direction = (direction + 1) % 4;
		}
		++move_length;
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	init();
	cin >> N;
	for (int ix = 1, iy; ix <= N; ++ix)
		for (iy = 1; iy <= N; ++iy)
			cin >> arr[ix][iy];
	solve((N + 1) / 2, (N + 1) / 2);
	cout << result << endl;
	return 0;
}
// *&)*@*

1. 문제에서의 예시는 바람이 좌측일때, 그리고 현재 y의 위치에 왔을때, y를 각각의 퍼센트만큼 나눠주고 남은 모래를 다시 a에게 모두 주는게 요지입니다.
2. 즉, 모든 좌측은 1번과 동일하게 y 위치 기준 각각의 위치에 퍼센트만큼 나눠주면 됩니다. 여기서 나눠주는 범위가 격자를 넘어가는 경우는 격자 밖으로 나간 모래들입니다. 즉, 격자 안이라면 해당 격자에 모래를 더해주고 격자 밖이라면 결과값에 보태어줍니다.
3. 예시는 좌측의 경우이므로, 우측은 예시를 180도 돌렸을때의 퍼센트 위치가 정해집니다. (북측, 남측도 마찬가지입니다.)
4. 결국 토네이도 방향으로 배열을 이동시킬 수 있고, 이동한 배열의 값이 0보다 크면, 토네이도에 의해 모래값이 퍼센트에 의해 이동되고 a로 나머지가 모두 이동됩니다.