<Baekjoon> #20057 BFS_마법사 상어와 토네이도 c++

#20057 마법사 상어와 토네이도
참고

그림을 보고 모래가 움직이는 순서를 차례대로 살펴보면

다음과 같음을 알 수 있다.
1. dir 방향으로 dist 만큼 이동 (dir-서,남,동,북, dist-1부터 시작)

• 1-1. 이동할 때 9방향으로 모래가 퍼짐
• 1-2. 나머지가 a에 저장

2. dir 방향 변경
3. dir 방향으로 dist 만큼 이동

• 3-1. 이동할 때 9방향으로 모래가 퍼짐
• 3-2. 나머지가 a에 저장

4. dir 방향 변경, dist=dist+1

다음 모래가 각 위치에 퍼지는 비율을 저장하는데 오른쪽 그림과 같은 순서의 비율로 모래를 저장하면 double p[9] = { 0.05, 0.1, 0.1, 0.02, 0.02, 0.07, 0.07, 0.01, 0.01 } 와 같다

모래는 서-남-동-북의 순서대로 움직이는데 이를 차례대로 그림과 같이 좌표로 나타내보면

int m_dy[4][10] = { 
					{0,-1,1,-2,2,-1,1,-1,1,0}, //west
					{2,1,1,0,0,0,0,-1,-1,1}, //south
					{0,-1,1,-2,2,-1,1,-1,1,0}, //east
					{-2,-1,-1,0,0,0,0,1,1,-1} //north
                    }; 
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}
                    };

1. 처음 위치 (N/2, N/2), 처음 방향 dir=0 (west), 처음 이동 거리 dist=1

	int dir = 0; //0=w, 1=s, 2=e, 3=n
	int dist = 1;
	int y = N / 2, x = N / 2;

• 현재 위치 (y,x)에서 dir방향으로 이동거리 dist만큼 이동한 위치를 (ny, nx)에 저장하고 현재 위치를 이동한 위치로 바꾸어준다.
• 문제에서 x에서 y로 이동하면 y위치에 있는 모든 모래는 9방향과 a로 이동한다고 되어 있으니 모래의 총 양을 a라는 변수에 저장해준다 (변수명을 겹치게 써놔서 헷갈린다..잘못했다..)

		for (int i = 0; i < dist; i++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			y = ny, x = nx; //현재 위치로 
			a = map[ny][nx]; //이동한 모래의 양 저장
            ......
        }

2. 이동한 위치에서 9방향으로 모래가 흩어짐

• dir 방향으로 이동할 때 0,1,...,8번째 방향으로 퍼질 위치를 (m_ny, m_nx)로 지정
• 이동한 위치에 있던 모래의 양 (map[ny][nx])에 각 위치의 모래 비율 (p[j])을 곱해주어 sand에 저장하고 위에서 원래 모래의 양(a)에서 빼준다.
• (m_ny, n_ny)가 map의 범위를 벗어나면 구하려는 값이므로 result에 모래의 양 (sand)를 더해 저장해주고 범위 내에 있으면 해당 위치에 더해준다.

			for (int j = 0; j < 9; j++) {
				int m_ny = ny + m_dy[dir][j];
				int m_nx = nx + m_dx[dir][j];

				//흩어지는 모래의 비율
				int sand = (int)(map[ny][nx] * p[j]);
				a -= sand;

				//out of range->add result
				if (m_ny < 0 || m_nx < 0 || m_ny >= N || m_nx >= N)
					result += sand;
				else
					map[m_ny][m_nx] += sand;
			}

3. 나머지를 a에 저장
   
   2번에서 9방향에 모두 모래를 저장하고 남은 모래를 그림에서 a위치에 저장한다. a의 위치는 m_dy[][9], m_dx[][9]
   (그림에서 a랑 코드에서 변수 a는 다른 것)

			int ay = ny + m_dy[dir][9];
			int ax = nx + m_dx[dir][9];

			if (ay < 0 || ax < 0 || ay >= N || ax >= N)
				result += a;
			else
				map[ay][ax] += a;

4. dir, dist 변경

• 모든 모래는 9방향과 a 위치로 흩어졌으므로 원래 위치에서 이동한 위치에 있던 모래 양을 0으로 바꾸어주고, 그 위치가 (0,0)이면 중단한다

			map[ny][nx] = 0;
			if (ny == 0 && nx == 0) return result;

• cnt 변수를 두어 2번 반복할 때마다 dist를 1씩 늘려주고 방향은 매번 바꾸어준다

		if (cnt == 2) {
			dist++;
			cnt = 0;
		}
		dir = (dir + 1) % 4;

전체 코드

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> map;
double p[9] = { 0.05, 0.1, 0.1, 0.02, 0.02, 0.07, 0.07, 0.01, 0.01 };
int m_dy[4][10] = { 
									{0,-1,1,-2,2,-1,1,-1,1,0}, //west
									{2,1,1,0,0,0,0,-1,-1,1}, //south
									{0,-1,1,-2,2,-1,1,-1,1,0}, //east
									{-2,-1,-1,0,0,0,0,1,1,-1} //north
}; 
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 dy[4] = { 0, 1, 0, -1 };
int dx[4] = { -1, 0, 1, 0 };


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

int  solution() {
	int result = 0;
	int cnt = 0;
	int a;
	int dir = 0; //0=w, 1=s, 2=e, 3=n
	int dist = 1;
	int y = N / 2, x = N / 2;

	while (1) {
		cnt++;
		
		//dist 만큼 dir방향으로 현재 위치 이동
		for (int i = 0; i < dist; i++) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			y = ny, x = nx; //현재 위치로 
			a = map[ny][nx]; //이동한 모래의 양 저장

			//dir 방향으로 바람이 불 때 9방향으로 흩어지는 모래들
			for (int j = 0; j < 9; j++) {
				int m_ny = ny + m_dy[dir][j];
				int m_nx = nx + m_dx[dir][j];

				//흩어지는 모래의 비율
				int sand = (int)(map[ny][nx] * p[j]);
				a -= sand;

				//out of range->add result
				if (m_ny < 0 || m_nx < 0 || m_ny >= N || m_nx >= N)
					result += sand;
				else
					map[m_ny][m_nx] += sand;
			}
			int ay = ny + m_dy[dir][9];
			int ax = nx + m_dx[dir][9];

			//나머지 남아 있는 모래를 a에
			if (ay < 0 || ax < 0 || ay >= N || ax >= N)
				result += a;
			else
				map[ay][ax] += a;

			//y의 모든 모래는 a와 9방향으로 흩어졌으므로
			map[ny][nx] = 0;
			if (ny == 0 && nx == 0) return result;
		}
		if (cnt == 2) {
			dist++;
			cnt = 0;
		}
		dir = (dir + 1) % 4;
	}
}

int main() {
	init();
	cout << solution() << endl;
	return 0;
}

변수도 너무 많고 좌표 만드는 것도 너무 까다로워서 진짜 힘든 문제였다..