[백준/BOJ] 20057 - 마법사 상어와 토네이도 (c++)

이 문제는 구현문제로 어떻게 구현할지 생각하는데 조금 생각해봐야하는 문제이다.

 

특별하게 생각해야할 점은 아래의 두점이다.

 

• 토네이도가 이동하는 경로

토네이도는 1칸가고 방향바꾸고, 1칸가고 방향바꾸고, 2칸가고 방향바꾸고, 2칸가고 방향바꾸고, 3칸가고 방향바꾸고....

 

이러한 규칙을 통해 토네이도의 가는 경로를 쉽게 구현해 낼 수 있었다.

 

• 토네이도의 방향에따라 달라지는 모래가 날리는 좌표

토네이도가 상하좌우 방향에 따라 모래가 날리는 좌표가 조금씩 달라지는데

 

한번 모든 방향 4가지의 좌표를 계산해봐서 연관성을 찾아본다면

 

방향이 180도 다른 것의 좌표는 x축 또는 y축 대칭이라는 것을 알 수 있다.

 

방향이 90도 다른 것들의 좌표는 y=x(45도의 직선) 대칭이라는 것을 알 수 있다.

 

따라서 하나의 방향의 좌표들을 구한 뒤 나머지 3개의 방향에 대한 좌표를 알맞게 배치해두고 구현을 하면 쉽게 된다.

 

---

소스코드

 

#include <iostream>

using namespace std;

int x, y, d;

int N, sand[499][499], ans = 0;
int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 }; //0:l, 1:d, 2:r, 3:u
int sx[10] = { 0,-1,1,-2,-1,1,2,-1,1,0 }, sy[10] = { -2,-1,-1,0,0,0,0,1,1,-1 }, sc[10] = { 5,10,10,2,7,7,2,1,1,0 };
/*
* d에 따라 s값이 바뀜
* d: -sx<->-sy
* r: -sx, -sy
* u: sx<->sy
*/ 

void Input() {
	cin >> N;
	x = y = N / 2;
	d = 0;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> sand[i][j];
		}
	}
}

void Solution() {
	int move = 0, maxMove = 1, flag = 1;
	while (true) {
		if (x == 0 && y == 0) break;

		if (move == maxMove) {
			move = 0;
			if (flag == 2) {
				flag = 0;
				maxMove++;
			}
			d = (d + 1) % 4;
			flag++;
		}

		int tnx = x + dx[d], tny = y + dy[d], tns = sand[tnx][tny];
		move++;

		int snx, sny, sna;
		for (int i = 0; i < 10; i++) {
			if (d == 0) {
				snx = tnx + sx[i], sny = tny + sy[i], sna = i == 9 ? sand[tnx][tny] : tns * sc[i] / 100;
				sand[tnx][tny] -= sna;
				if (snx < 0 || sny < 0 || snx >= N || sny >= N)ans += sna;
				else sand[snx][sny] += sna;
			}
			else if (d == 1) {
				snx = tnx - sy[i], sny = tny - sx[i], sna = i == 9 ? sand[tnx][tny] : tns * sc[i] / 100;
				sand[tnx][tny] -= sna;
				if (snx < 0 || sny < 0 || snx >= N || sny >= N)ans += sna;
				else sand[snx][sny] += sna;
			}
			else if (d == 2) {
				snx = tnx - sx[i], sny = tny - sy[i], sna = i == 9 ? sand[tnx][tny] : tns * sc[i] / 100;
				sand[tnx][tny] -= sna;
				if (snx < 0 || sny < 0 || snx >= N || sny >= N)ans += sna;
				else sand[snx][sny] += sna;
			}
			else {
				snx = tnx + sy[i], sny = tny + sx[i], sna = i == 9 ? sand[tnx][tny] : tns * sc[i] / 100;
				sand[tnx][tny] -= sna;
				if (snx < 0 || sny < 0 || snx >= N || sny >= N)ans += sna;
				else sand[snx][sny] += sna;
			}
		}

		x = tnx, y = tny;
	}

	cout << ans;
}

int main() {
	ios::sync_with_stdio(0);
	Input();
	Solution();
}