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

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

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

문제

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

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다.

다음은 N = 7인 경우 토네이도의 이동이다.

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

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

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

 

 

문제 풀이

이 문제는 나선형의 규칙만 찾는다면 쉽게 풀 수 있다

여기서 나선형 규칙은 다음과 같다.

기본 이동 거리 dist = 1, dir = 서쪽이라고 생각하자. 

1. dir 방향으로 dist 만큼 이동한다.
2. dir를 회전한다.
3. 회전한 dir 방향으로 dist만큼 이동한다.
4. dir를 회전하고, dist에 1을 추가한다.

즉, 두 번 방향을 바꿀 때 마다 한 방향으로 이동하는 거리를 1 증가시키면 된다.

위와 같이 나선형으로 위치를 변경시키며, 모래 사장 밖으로 벗어난 모래 (배열 index를 벗어난 경우)를 모두 더하여 출력하면 된다.

 

또한 흩날리는 모래는 다음의 dy, dx 2차원 배열과 비율에 대한 1차원 배열을 이용하여 쉽게 구할 수 있다.

// 움직이는 모래의 정도
double p[9] = { 0.05, 0.1, 0.1, 0.02, 0.02, 0.07, 0.07, 0.01, 0.01 };
/*
 * 움직이는 모래에 대한 dy, dx 2차원 벡터
 * 첫 번째 차원은 방향
 * 두 번째 차원은 방향에 따라 움직이는 모래의 dy, dx
*/
int m_dy[4][10] = {
	{0,-1,1, -2,2,-1,1,-1,1,0}, //서
	{2,1,1,0,0,0,0,-1,-1,1},    //남
	{0,-1,1, -2,2,-1,1,-1,1,0}, //동
	{-2,-1,-1,0,0,0,0,1,1,-1}   //북
};
int m_dx[4][10] = {
	{-2,-1,-1,0,0,0,0,1,1,-1},  //서
	{0,-1,1, -2,2,-1,1,-1,1,0}, //남
	{2,1,1,0,0,0,0,-1,-1,1},    //동
	{0,-1,1, -2,2,-1,1,-1,1,0}  //북
};

 

소스코드

#include <iostream>
#include <vector>
int N;

using namespace std;
vector<vector<int> > board;

//4방향
int dy[] = { 0,1,0,-1 };
int dx[] = { -1, 0,1,0 };

// 움직이는 모래의 정도
double p[9] = { 0.05, 0.1, 0.1, 0.02, 0.02, 0.07, 0.07, 0.01, 0.01 };
/*
 * 움직이는 모래에 대한 dy, dx 2차원 벡터
 * 첫 번째 차원은 방향
 * 두 번째 차원은 방향에 따라 움직이는 모래의 dy, dx
*/
int m_dy[4][10] = {
	{0,-1,1, -2,2,-1,1,-1,1,0},
	{2,1,1,0,0,0,0,-1,-1,1},
	{0,-1,1, -2,2,-1,1,-1,1,0},
	{-2,-1,-1,0,0,0,0,1,1,-1}
};
int m_dx[4][10] = {
	{-2,-1,-1,0,0,0,0,1,1,-1},
	{0,-1,1, -2,2,-1,1,-1,1,0},
	{2,1,1,0,0,0,0,-1,-1,1},
	{0,-1,1, -2,2,-1,1,-1,1,0}
};
int result = 0;
int cnt = 0;

void check() {
	int y = N / 2, x = N / 2; // 배열의 중간 좌표
	int a;
	int dist = 1;
	int d = 0; // 방향 정보 ( 0 : 서, 1 : 남, 2 : 동, 3 : 북)
	int cnt = 0; // 두 번 이동 확인용 count 변수
	while (1) {
		cnt++;

		//dist만큼 d방향으로 이동
		for (int m = 0; m < dist; m++) { 
			int ny = y + dy[d];  // d 방향으로 이동
			int nx = x + dx[d];  // d 방향으로 이동
			y = ny;
			x = nx;
			a = board[ny][nx]; // 이동한 모래 
			for (int k = 0; k < 9; k++) {
				int m_ny = ny + m_dy[d][k]; //흩날리는 모래 y 좌표
				int m_nx = nx + m_dx[d][k]; //흩날리는 모래 x 좌표

				int sand = (int)(board[ny][nx] * p[k]); //흩날리는 모래 양
				a -= sand; // 이동한 모래에서 흩날리는 모래를 빼줌
				if (m_ny < 0 || m_ny >= N || m_nx < 0 || m_nx >= N)  // 격자 밖으로 이동한 경우 result에 흩날린 모래를 추가
					result += sand; 
				else   // 격자 안인 경우 해당 좌표에 흩날리는 모래 양 추가
					board[m_ny][m_nx] += sand; 
				
			}
			//나머지 모래 이동
			int m_ny = ny + m_dy[d][9]; 
			int m_nx = nx + m_dx[d][9];
			if (m_ny < 0 || m_ny >= N || m_nx < 0 || m_nx >= N) {
				result += a;
			}
			else
				board[m_ny][m_nx] += a;

			board[ny][nx] = 0; // 이동 후 모래 = 0으로 지정
			if (ny == 0 && nx == 0) //이동 후 좌표가 (0, 0)인 경우 종료
				return;
		}
		if (cnt == 2) {  
			//두 번 이동한 경우 dist+=1
			dist++;
			cnt = 0;
		}
		d = (d + 1) % 4; // 이동 방향을 바꿈
	}
}
int main()
{
	//입력
	cin >> N;
	board = vector<vector<int> >(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	//모래 이동
	check();

	//결과 출력
	cout << result;
}