[C++][백준] 마법사 상어와 토네이도(20057)

문제

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

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

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

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

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

 

출력

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

 

풀이

먼저 토네이도의 이동 경로부터 생각해보겠습니다.

크기가 N * N인 격자에서 토네이도 시작 위치는 (N/2, N/2)입니다. 

 

(N/2, N/2) 위치에서 시계 반대방향으로 토네이도가 이동하게 되는데요 아래와 같은 규칙성이 존재합니다.

시작 위치로부터 (왼쪽 1번, 아래 1번), (오른쪽 두번, 위로 2번), (왼쪽 3번, 아래 3번) ... 규칙을 따라 움직이게되며 (0, 0) 위치에서 종료됩니다.

 

해당 코드는 아래와 같습니다.

int cnt = 1;
while (1) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < cnt; j++) {
		// 토네이도가 이동한다.
			windX = windX + dirX[windDir];
			windY = windY + dirY[windDir];
	
			moveAll(windX, windY, windDir);

			if (windX == 0 && windY == 0) break;
		}
		if (windX == 0 && windY == 0) break;
		windDir = (windDir + 1) % 4;
	}
	if (windX == 0 && windY == 0) break;
	cnt++;
}

토네이도의 위치가 (windX, windY)일 때, 아래 과정을 반복합니다.

(1) 특정 방향으로 cnt만큼 이동합니다. (종료 지점이라면 종료합니다.)

(2) 시계 반시계 방향으로 방향을 틉니다.

(3) 바뀐 방향으로 cnt만큼 이동합니다.

(4) 시계 반시계 방향으로 방향을 틉니다.

(5) cnt를 1증가 시킵니다.

 

moveAll(int windX, int windY, int windDir) 함수는 토네이도가 (windX, windY) 좌표로 이동했을때, 모든 모래를 휘날립니다. 

move(int x, int y, int originalSand, double rate) 함수는 (x, y) 격자에 originalSand양의 모래를 rate 비율로 보내는 함수입니다. 보내진 모래양을 반환합니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N;
int map[510][510];

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {-1, 0, 1, 0};

int windX;
int windY;
int windDir = 0;

int answer = 0;

bool IsInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	else return false;
}

int move(int x, int y, int originalSand, double rate) {
	if (IsInRange(x, y)) map[x][y] += originalSand * rate;
	else answer += originalSand * rate;
	return originalSand * rate;
}

void moveAll(int windX, int windY, int windDir) {
	int originalSand = map[windX][windY];
	int blowSand = 0;

	if (windDir == 0) { // ←
		blowSand += move(windX - 2, windY, originalSand, 0.02);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX - 1, windY, originalSand, 0.07);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX, windY - 2, originalSand, 0.05);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX + 1, windY, originalSand, 0.07);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX + 2, windY, originalSand, 0.02);

		if (IsInRange(windX, windY - 1)) map[windX][windY - 1] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 1) {
		blowSand += move(windX - 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX, windY - 2, originalSand, 0.02);
		blowSand += move(windX, windY - 1, originalSand, 0.07);
		blowSand += move(windX, windY + 1, originalSand, 0.07);
		blowSand += move(windX, windY + 2, originalSand, 0.02);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX + 2, windY, originalSand, 0.05);

		if (IsInRange(windX + 1, windY)) map[windX + 1][windY] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 2) {
		blowSand += move(windX - 2, windY, originalSand, 0.02);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX - 1, windY, originalSand, 0.07);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX, windY + 2, originalSand, 0.05);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX + 1, windY, originalSand, 0.07);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX + 2, windY, originalSand, 0.02);

		if (IsInRange(windX, windY + 1)) map[windX][windY + 1] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 3) {
		blowSand += move(windX - 2, windY, originalSand, 0.05);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX, windY - 2, originalSand, 0.02);
		blowSand += move(windX, windY - 1, originalSand, 0.07);
		blowSand += move(windX, windY + 1, originalSand, 0.07);
		blowSand += move(windX, windY + 2, originalSand, 0.02);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.01);

		if (IsInRange(windX - 1, windY)) map[windX - 1][windY] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	map[windX][windY] = 0;
}

int main() {
	cin >> N;
	windX = N / 2;
	windY = N / 2;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	int cnt = 1;
	while (1) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < cnt; j++) {
				// 토네이도가 이동한다.
				windX = windX + dirX[windDir];
				windY = windY + dirY[windDir];

				moveAll(windX, windY, windDir);

				if (windX == 0 && windY == 0) break;
			}
			if (windX == 0 && windY == 0) break;
			windDir = (windDir + 1) % 4;
		}
		if (windX == 0 && windY == 0) break;
		cnt++;
	}

	cout << answer;

	return 0;
}