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

 

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

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

 

- 빡구현 문제이다. 시간복잡도는 모든 칸을 순회하면서 각 칸에서 모래를 이동시키므로(상수연산) O(N^2)이다.

 

- 필자는 먼저, 각 칸의 다음 이동 방향을 dir배열에 구현했다. 그 후, 이 방향을 기반으로 하여 토네이도가 이동한 후 흩날리는 모래들을 구해서 각 칸에 넣어주는 식으로 구현을 했다.

 

- 방향을 구하는 과정은

 

1. 먼저, 해당 칸의 방향 최신화

2. 다음으로, 해당 방향으로 forward_num만큼 이동하면서 방향 최신화

3. 마지막으로 now_x와 now_y, 그 칸에 들어가야 할 dir까지 최신화

4. 만약 now_x == 0 , now_y == -1이 되었다면 break

 

이 과정을 반복했다. 여기서, forward_num은 토네이도가 방향이 2번 바뀔 때 마다 +1을 해 주는 규칙을 잘 반영했다.

 

- 방향을 구한 다음은 쉽다. 주어진 조건에 맞게 모래들을 각 칸에 넣어주기만 하면 된다.(근데 매우 귀찮다.)

 

- 코드를 최대한 짧게 구현하려다보니 for문에 중괄호를 안 쓰는 문제를 일으켜서 디버깅을 좀 했다. 또, 모래를 각 칸에 넣어주는 과정을 구현할 때 집중을 안 하면 오타가 발생할 확률이 높으니 집중해서 구현을 해야 한다.

 

#include <iostream>
using namespace std;
int map[500][500]; int dir[500][500];
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
int n;
void debugging() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
void make_dir(int start_x, int start_y) {
	int now_dir = 6;
	int forward_num = 0;
	int now_x = start_x; int now_y = start_y;
	bool is_completed = false;
	while (1) { //dir 배열에 모든 칸의 방향값을 대입한다.
		for (int i = 0; i < 2; i++) {
			dir[now_x][now_y] = now_dir;
			for (int j = 0; j < forward_num; j++) {
				now_x += dx[now_dir]; now_y += dy[now_dir];
				dir[now_x][now_y] = now_dir;
			}
			now_x += dx[now_dir]; now_y += dy[now_dir];
			now_dir = (now_dir + 6) % 8;
			if (now_x == 0 && now_y == -1) {
				is_completed = true; break;
			}
		}
		forward_num++;
		if (is_completed) return; // 모든 칸에 방향값을 대입했다면, 함수 종료
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	int now_x = n / 2; int now_y = n / 2;
	make_dir(now_x, now_y);
	int answer = 0;
	while (!(now_x == 0 && now_y == 0)) {
		int now_dir = dir[now_x][now_y];
		int next_x = now_x + dx[now_dir]; int next_y = now_y + dy[now_dir];
		int now_sand = map[next_x][next_y]; // y좌표의 총 모래
		int ten_percent = now_sand / 10; int seven_percent = now_sand * 0.07; int two_percent = now_sand / 50;
		int one_percent = now_sand / 100; int five_percent = now_sand / 20;
		int alpha = now_sand - five_percent - (2 * ten_percent) - (2 * seven_percent) - (2 * one_percent) - (2 * two_percent);

		// 5% 처리
		int five_percent_x = next_x; int five_percent_y = next_y;
		for (int i = 0; i < 2; i++) {
			five_percent_x += dx[now_dir]; five_percent_y += dy[now_dir];
		}
		if (five_percent_x < 0 || five_percent_x >= n || five_percent_y < 0 || five_percent_y >= n) answer += five_percent;
		else map[five_percent_x][five_percent_y] += five_percent;

		// 10% 처리
		int first_ten_percent_x = next_x + dx[(now_dir + 7) % 8]; int first_ten_percent_y = next_y + dy[(now_dir + 7) % 8];
		if (first_ten_percent_x < 0 || first_ten_percent_x >= n || first_ten_percent_y < 0 || first_ten_percent_y >= n) answer += ten_percent;
		else map[first_ten_percent_x][first_ten_percent_y] += ten_percent;
		
		int second_ten_percent_x = next_x + dx[(now_dir + 1) % 8]; int second_ten_percent_y = next_y + dy[(now_dir + 1) % 8];
		if (second_ten_percent_x < 0 || second_ten_percent_x >= n || second_ten_percent_y < 0 || second_ten_percent_y >= n) answer += ten_percent;
		else map[second_ten_percent_x][second_ten_percent_y] += ten_percent;

		// 2% 처리
		int first_two_percent_x = next_x; int first_two_percent_y = next_y;
		int first_two_percent_dir = (now_dir + 6) % 8; 
		for (int i = 0; i < 2; i++) {
			first_two_percent_x += dx[first_two_percent_dir]; first_two_percent_y += dy[first_two_percent_dir];
		}
		if (first_two_percent_x < 0 || first_two_percent_x >= n || first_two_percent_y < 0 || first_two_percent_y >= n) answer += two_percent;
		else map[first_two_percent_x][first_two_percent_y] += two_percent;

		int second_two_percent_x = next_x; int second_two_percent_y = next_y;
		int second_two_percent_dir = (now_dir + 2) % 8;
		for (int i = 0; i < 2; i++) {
			second_two_percent_x += dx[second_two_percent_dir]; second_two_percent_y += dy[second_two_percent_dir];
		}
		if (second_two_percent_x < 0 || second_two_percent_x >= n || second_two_percent_y < 0 || second_two_percent_y >= n) answer += two_percent;
		else map[second_two_percent_x][second_two_percent_y] += two_percent;

		// 7% 처리
		int first_seven_percent_x = next_x + dx[(now_dir + 6) % 8]; int first_seven_percent_y = next_y + dy[(now_dir + 6) % 8];
		if (first_seven_percent_x < 0 || first_seven_percent_x >= n || first_seven_percent_y < 0 || first_seven_percent_y >= n) answer += seven_percent;
		else map[first_seven_percent_x][first_seven_percent_y] += seven_percent;

		int second_seven_percent_x = next_x + dx[(now_dir + 2) % 8]; int second_seven_percent_y = next_y + dy[(now_dir + 2) % 8];
		if (second_seven_percent_x < 0 || second_seven_percent_x >= n || second_seven_percent_y < 0 || second_seven_percent_y >= n) answer += seven_percent;
		else {
			map[second_seven_percent_x][second_seven_percent_y] += seven_percent;
		}
		// 1% 처리
		int first_one_percent_x = next_x + dx[(now_dir + 5) % 8]; 	int first_one_percent_y = next_y + dy[(now_dir + 5) % 8];
		if (first_one_percent_x < 0 || first_one_percent_x >= n || first_one_percent_y < 0 || first_one_percent_y >= n) answer += one_percent;
		else map[first_one_percent_x][first_one_percent_y] += one_percent;

		int second_one_percent_x = next_x + dx[(now_dir + 3) % 8]; 	int second_one_percent_y = next_y + dy[(now_dir + 3) % 8];
		if (second_one_percent_x < 0 || second_one_percent_x >= n || second_one_percent_y < 0 || second_one_percent_y >= n) answer += one_percent;
		else map[second_one_percent_x][second_one_percent_y] += one_percent;
		
		// alpha 처리
		int	alpha_x = next_x + dx[now_dir]; int alpha_y = next_y + dy[now_dir];
		if (alpha_x < 0 || alpha_x >= n || alpha_y < 0 || alpha_y >= n) answer += alpha;
		else map[alpha_x][alpha_y] += alpha;
		map[next_x][next_y] = 0;
		now_x = next_x; now_y = next_y;
	}
	cout << answer;
	return 0;
}