boj, 백준) 20057. 마법사 상어와 토네이도 ( C/C++)

1. 문제 링크

www.acmicpc.net/problem/20057

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

 

2. 문제 개요

토네이도를 크기가 N x N인 격자로 나누어진 모래밭에서 연습하려고 한다.  각 격자에는 모래가 일정량 쌓여있고, 토네이도가 오면 주변으로 흩날리게 된다. 

모래밭의 바깥으로 나간 모래의 총량을 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

(1) 토네이도의 경로

   - 1,1 / 2,2 / 3,3/ ... / n-1,n-1,n-1칸 이동하는 것을 볼 수 있다.

   - 서, 남, 동, 북 ... 순으로 회전하는 것을 알 수 있다.

 

(2) 토네이도의 진행 방향 별 흩날리는 것 구현

   - y를 기준으로 방향 별 흩날리는 좌표를 사전에 저장하자.

서

 

남  동  북

서쪽을 예로들면 y를 기준으로 (-2, 0)좌표에 2%가 있다. y를 기준으로 (-1,-1)좌표에 10%가 있다. 이런 식으로 구현할 수 있겠다.

 

이것 2개만 잘 생각해보자.

 

 

4. 문제 풀이

문제에서 조금 생각해봐야 하는 부분은 3번 문제힌트의 (1), (2) 번 밖에 없다. 그 외에는 어떻게 하면 문제의 절차를 코드로 잘 옮길 수 있느냐가 관건.

 

문제를 읽어보면,

맵의 중심에서 토네이도가 움직이는데,

움직이는 곳에 모래가 있으면 모래가 퍼진다.

모래가 퍼지는데, 그곳에 모래가 있다면 모래의 양은 더해진다.

모래장 밖으로 나가는 모래의 합은?

 

이 4가지가 중점이다.

 

토네이도가 움직이는 규칙을 보면, '서 남 동 북' 순서대로 회전하는 것을 알 수 있고,

이것은 1, -1의 부호로 나타낼 수 있다. (코드의 dx, dy, dir)

 

거리 또한 1,1 / 2,2 / ... / n-1, n-1, n-1으로 움직이는데,

 

1~n-1까지 반복하되,

1~n-2일때는 반복을 2번, n-1일 때는 반복을 3번 이런 방식으로 거리도 구현해줄 수 있다.

 

위의 방식으로 토네이도가 움직이는 것을 구현했다.

 

모래가 퍼지는 것을 3.문제힌트의 (2) 번의 그림 4개를 모두 손수 입력해주었다.

코드에서는 pair<COORD,int> spread[4][10]이다.

첫 번째 인덱스는 방향, 두 번째 인덱스는 위치를 나타낸다. 배열의 값(방향에 해당하는 위치의 값)으로는 중심(y)과 얼마나 떨어져 있는지(COORD), 그리고 몇%의 모래가 퍼지는지(int)를 갖는다.

spread[4][0~8]까지는 퍼지는 곳이고 [9]는 a를 나타낸다.

 

 

여기까지 정의하면 문제에서 말하는 순서대로 코드로 옮기면 된다.

a는 모두 이동한 나머지를 말하고 있기 때문에, 모래들이 다 퍼지고난 뒤의 남은 모래를 계산하여 옮겨주어야 한다.

 

 

구현/시뮬레이션 문제이기 때문에 이 이외의 부분은 코드를 보는 것이 좋을 것 같습니다^_^

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

struct COORD {
	COORD() {}
	COORD(int y_, int x_) :y(y_), x(x_) {}
	int y, x;
};
int n;
int A[500][500];
COORD cur;

const int dx[] = { -1,0,1,0 };	//W,S,E,N
const int dy[] = { 0,1,0,-1 };
int dir, dist, ans;

//y, W,S,E,N
const pair<COORD, int> spread[4][10] = 
{ {{COORD(-2,0),2},{COORD(-1,-1),10},{COORD(-1,0),7},{COORD(-1,1),1},{COORD(0,-2),5},{COORD(1,-1),10},{COORD(1,0),7},{COORD(1,1),1},{COORD(2,0),2},{COORD(0,-1),0}} ,
 {{COORD(-1,-1),1},{COORD(-1,1),1},{COORD(0,-2),2},{COORD(0,-1),7},{COORD(0,1),7},{COORD(0,2),2},{COORD(1,-1),10},{COORD(1,1),10},{COORD(2,0),5},{COORD(1,0),0}} ,
 {{COORD(-2,0),2},{COORD(-1,-1),1},{COORD(-1,0),7},{COORD(-1,1),10},{COORD(0,2),5},{COORD(1,-1),1},{COORD(1,0),7},{COORD(1,1),10},{COORD(2,0),2},{COORD(0,1),0}} ,
 {{COORD(1,-1),1},{COORD(1,1),1},{COORD(0,-2),2},{COORD(0,-1),7},{COORD(0,1),7},{COORD(0,2),2},{COORD(-1,-1),10},{COORD(-1,1),10},{COORD(-2,0),5},{COORD(-1,0),0}}
};

int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			scanf("%d", &A[i][j]);

	cur = COORD((1 + n) / 2, (1 + n) / 2);

	//move
	for (dist = 1; dist < n; ++dist) {

		int iter = 2;

		if (dist == n-1)
			iter = 3;

		for (int j = 1; j <= iter; ++j) {
			for (int k = 1; k <= dist; ++k) {

				COORD next;
				next.x = cur.x + dx[dir];
				next.y = cur.y + dy[dir];

				if (A[next.y][next.x] != 0) {
					//spread
					int sand = A[next.y][next.x];
					A[next.y][next.x] = 0;
					int sumofspreadsand = 0;
					COORD spread_sand;
					for (int i = 0; i < 10; ++i) {
						spread_sand.y = next.y + spread[dir][i].first.y;
						spread_sand.x = next.x + spread[dir][i].first.x;

						int amount = 0;
						if (i < 9) {
							amount = sand * spread[dir][i].second / 100;
							sumofspreadsand += amount;	//sand is blown
						}
						else {
							//for a
							amount = sand - sumofspreadsand;
						}

						if (spread_sand.y<1 || spread_sand.x<1 || spread_sand.y>n || spread_sand.x >n)
						{
							ans += amount;
							continue;
						}
						A[spread_sand.y][spread_sand.x] += amount;
					}
				}
				cur = next;
			}
			dir = (dir + 1) % 4;	//next dir
		}
	}
	
	printf("%d", ans);

	return 0;
}

 

6. 결과