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

풀이 소요시간 : 55분

최근 풀어본 문제중 역대급 깡구현 인내심을 요구했다.
구현 + 시뮬레이션으로 골드3 의 난이도니까 말 다했다.

삼성 기출이다보니 실제 코딩테스트라고 생각하고 나름 집중해서 풀었다. 역시 삼성 기출 골드3 의 난이도라고 하지만 프로그래머스 카카오 기출 Lv.2 보다 쉬웠다.

실제 구현은 40분정도에 마무리 지었지만, 방향 하나를 실수해서 테스트케이스중 일부가 통과되지 않았고 시간을 더 소모했다. 이정도의 구현을 하는데는 집중력과 운이 필수로 따라줘야한다.

다 풀고 다른 풀이도 참고했는데 결국 실수없이 구현하는게 중요했다.
다만 좌표를 배열화 해둔 풀이가 많았다. 참고해봐야겠다.

전체 코드

#include<iostream>
using namespace std;

int N;
int sx, sy;
int Map[500][500];

//토네이도의 진행 방향 순서
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
int Ans = 0;
int A;

void Input() {
	cin >> N;
	sx = N / 2 + 1;
	sy = N / 2 + 1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> Map[i][j];
		}
	}
}


void Check(int x, int y, int p, int Total) {

	int sand = Total * p / 100;
	//소수점 아래는 버린다.

	if (x < 1 || y < 1 || x > N || y > N) {
		Ans += sand;
		A -= sand;
	}
	else {
		Map[x][y] += sand;
		A -= sand;
	}
}

void Sand(int x, int y, int Dir) {

	int Total = Map[x][y]; //해당 칸에 있던 모래의 양
	A = Total;
	Map[x][y] = 0;

	if (Dir == 0)
	{
		Check(x - 1, y + 1, 1, Total);
		Check(x + 1, y + 1, 1, Total);

		Check(x - 2, y, 2, Total);
		Check(x + 2, y, 2, Total);

		Check(x, y - 2, 5, Total);

		Check(x - 1, y, 7, Total);
		Check(x + 1, y, 7, Total);

		Check(x - 1, y - 1, 10, Total);
		Check(x + 1, y - 1, 10, Total);

		int a_x = x;
		int a_y = y - 1;
		if (a_x < 1 || a_y < 1 || a_x > N || a_y > N)
		{
			Ans += A;
		}
		else
		{
			Map[a_x][a_y] += A;
		}
	}
	else if (Dir == 2)
	{
		Check(x - 1, y - 1, 1, Total);
		Check(x + 1, y - 1, 1, Total);

		Check(x - 2, y, 2, Total);
		Check(x + 2, y, 2, Total);

		Check(x, y + 2, 5, Total);

		Check(x - 1, y, 7, Total);
		Check(x + 1, y, 7, Total);

		Check(x - 1, y + 1, 10, Total);
		Check(x + 1, y + 1, 10, Total);

		int a_x = x;
		int a_y = y + 1;
		if (a_x < 1 || a_y < 1 || a_x > N || a_y > N)
		{
			Ans += A;
		}
		else
		{
			Map[a_x][a_y] += A;
		}
	}
	else if (Dir == 1)
	{
		Check(x - 1, y - 1, 1, Total);
		Check(x  -1, y + 1, 1, Total);

		Check(x, y - 2, 2, Total);
		Check(x, y + 2, 2, Total);

		Check(x + 2, y, 5, Total);

		Check(x, y + 1, 7, Total);
		Check(x, y - 1, 7, Total);

		Check(x + 1, y + 1, 10, Total);
		Check(x + 1, y - 1, 10, Total);

		int a_x = x + 1;
		int a_y = y;
		if (a_x < 1 || a_y < 1 || a_x > N || a_y > N)
		{
			Ans += A;
		}
		else
		{
			Map[a_x][a_y] += A;
		}
	}
	else if (Dir == 3)
	{
		Check(x + 1, y - 1, 1, Total);
		Check(x + 1, y + 1, 1, Total);

		Check(x, y - 2, 2, Total);
		Check(x, y + 2, 2, Total);

		Check(x - 2, y, 5, Total);

		Check(x, y + 1, 7, Total);
		Check(x, y - 1, 7, Total);

		Check(x - 1, y + 1, 10, Total);
		Check(x - 1, y - 1, 10, Total);

		int a_x = x - 1;
		int a_y = y;
		if (a_x < 1 || a_y < 1 || a_x > N || a_y > N)
		{
			Ans += A;
		}
		else
		{
			Map[a_x][a_y] += A;
		}
	}
}


void Move() {

	//거리, 방향
	int Dist = 1;
	int Dir = 0;

	//시작 토네이도 좌표
	int px = sx;
	int py = sy;

	while (true)
	{
		//같은 길이반큼 2번씩 이동함 : 방향은 다름
		for (int i = 0; i < 2; i++)
		{
			//Dist 길이만큼 1씩 이동함
			for (int k = 0; k < Dist; k++)
			{
				int nx = px + dx[Dir % 4];
				int ny = py + dy[Dir % 4];

				Sand(nx, ny, Dir % 4);

				px = nx;
				py = ny;
			}

			Dir++;
		}

		if (Dist == N - 1) break;
		else Dist++;
	}

	for (int k = 0; k < Dist; k++)
	{
		int nx = px + dx[0];
		int ny = py + dy[0];

		Sand(nx, ny, 0);

		px = nx;
		py = ny;
	}
	// 마지막 N-1 번의 이동

}

int main()
{
	Input();
	Move();
	cout << Ans << '\n';
}