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

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

www.acmicpc.net

문제

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

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

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

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

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

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

  • 3 ≤ N ≤ 499
  • N은 홀수
  • 0 ≤ A[r][c] ≤ 1,000
  • 가운데 칸에 있는 모래의 양은 0

예제 입력 1

5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 1

10

예제 입력 2

5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 2

85

예제 입력 3

7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

예제 출력 3

139

예제 입력 4

5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500

예제 출력 4

7501

예제 입력 5

5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0

예제 출력 5

283

예제 입력 6

9
193 483 223 482 858 274 847 283 748
484 273 585 868 271 444 584 293 858
828 384 382 818 347 858 293 999 727
818 384 727 373 636 141 234 589 991
913 564 555 827 0 999 123 123 123
321 321 321 983 982 981 983 980 990
908 105 270 173 147 148 850 992 113
943 923 982 981 223 131 222 913 562
752 572 719 590 551 179 141 137 731

예제 출력 6

22961

알고리즘 분류

  • 구현
  • 시뮬레이션

풀이

시작 지점은 무조건 가운데, 즉 (N/2, N/2)에서 시작하며, 서 → 남 → 동 → 북 순으로 방향이 바뀌고, 방향이 2번 바뀔 때마다 토네이도가 그 방향으로 이동하는 거리가 1씩 증가하게 된다. 그리고 마지막에는 N만큼의 거리를 이동하여 (1,1)에 도착하게 될 것이다. 따라서, 토네이도가 이동하는 거리가 N이 되었을 때 토네이도가 소멸하게 된다.

토네이도가 이동할 때, 모래가 흩날리는 방향과 비율을 각각 spreadY, spreadX, Sand_Percent라는 배열로 선언하였다.

α 칸으로 이동하는 경우를 빼고, 아홉 방향으로 흩날리는 모래의 양을 계산하고, 남은 모래의 양은 α 칸으로 이동시킨다. 여기서 모래가 격자 바깥으로 흩날리게 되면, 그 모래의 양을 answer 변수에 더한다.

이제 토네이도를 이동시키면서 모래가 흩날리는 과정을 계속 반복하면서 격자 바깥으로 빠져나간 모래의 양을 answer 변수에 계속 더한 후, 최종적으로 answer 변수를 출력하면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 506
#define INF 2e9

using namespace std;
int N;
int MAP[MAX][MAX];
pair<int, int> Start;
int moveY[4] = { 0,1,0,-1 };
int moveX[4] = { -1,0,1,0 };
/*
	서, 남, 동, 북쪽으로 이동할 때 모래가 흩날리는 방향 및 비율을 배열로 만들어준다.
*/
int spreadY[4][10] = { { -1,1,-1,1,-1,1,-2,2,0,0 }, 
					   { 0,0,1,1,2,2,1,1,3,2 },
					   { -1,1,-1,1,-1,1,-2,2,0,0 },
					   { 0,0,-1,-1,-2,-2,-1,-1,-3,-2 } };
int spreadX[4][10] = { { 0,0,-1,-1,-2,-2,-1,-1,-3,-2 },
					   { -1,1,-1,1,-1,1,-2,2,0,0 },
					   { 0,0,1,1,2,2,1,1,3,2 },
					   { -1,1,-1,1,-1,1,-2,2,0,0 } };
int Sand_Percent[9] = { 1,1,7,7,10,10,2,2,5 };
int moveLen = 1; // 처음 이동 거리는 1
int Direction = 0; // 처음 이동 방향은 서쪽
int Dir_Change = 0; // 방향을 바꾼 횟수, 2번 바꿨다면 이동 거리를 1 증가시키고 횟수를 0으로 초기화
int answer = 0; // 격자 바깥으로 나간 모래의 양

void Sand_Spread(int Y, int X, int YY, int XX, int Sand, int Dir) {
	int tmp = Sand;
	for (int i = 0; i < 9; i++) { // α가 적혀있는 칸을 제외한 9방향으로 흩날린 모래의 양을 계산해준다.
		int nextY = Y + spreadY[Dir][i];
		int nextX = X + spreadX[Dir][i];
		int Per = Sand_Percent[i];
		int Sand_Part = (tmp * Per) / 100;
		// 모래가 격자 바깥으로 이동한 경우
		if ((nextY < 0) || (nextY >= N) || (nextX < 0) || (nextX >= N)) {
			answer += Sand_Part;
		}
		else {
			MAP[nextY][nextX] += Sand_Part;
		}
		Sand -= Sand_Part;
		// 흩날린 모래의 양만큼 계속 빼주면 α가 적혀있는 칸으로 흩날릴 모래의 양만 남게 될 것이다.
	}
	int nextY = Y + spreadY[Dir][9];
	int nextX = X + spreadX[Dir][9];
	if ((nextY < 0) || (nextY >= N) || (nextX < 0) || (nextX >= N)) {
		answer += Sand;
	}
	else {
		MAP[nextY][nextX] += Sand;
	}
	MAP[YY][XX] = 0; // 모래가 다 흩날리고 나면 Y 칸에 남은 모래는 0이 될 것이다.
}

void Tornado(int Y, int X, int Dir, int Len) {
	int CurY = Y;
	int CurX = X;
	for (int l = 0; l < Len; l++) {
		/*
			토네이도는 Len만큼 이동하면서 한 칸 이동할 때마다 모래가 흩날린다.
			이동하며 모래가 흩날린 후 토네이도의 현재 위치를 계속 초기화시켜준다.
		*/
		int nextY = CurY + moveY[Dir];
		int nextX = CurX + moveX[Dir];
		if (MAP[nextY][nextX] > 0) { 
			int Sand = MAP[nextY][nextX];
			Sand_Spread(CurY, CurX, nextY, nextX, Sand, Dir);
		}
		CurY = nextY;
		CurX = nextX;
	}
	// Dir 방향으로 Len만큼의 이동이 끝나면 다음 이동을 위해서 토네이도의 출발지점을 초기화한다.
	Start = make_pair(CurY, CurX);
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> MAP[i][j];
		}
	}
	// 시작은 무조건 가운데 지점에서부터 시작한다.
	Start = make_pair(N / 2, N / 2);
	while (1) {
		// 토네이도가 Direction 방향으로 moveLen만큼 이동 
		Tornado(Start.first, Start.second, Direction, moveLen);
		// 방향 전환(서 -> 남 -> 동 -> 북)
		Direction++; 
		if (Direction == 4) {
			Direction = 0;
		}
		// 방향이 2번 바뀔 때마다 토네이도의 이동 거리가 1씩 증가
		Dir_Change++;
		if (Dir_Change == 2) {
			Dir_Change = 0;
			moveLen++;
		}
		// 토네이도가 N만큼 이동하는 경우에는 토네이도가 (1, 1)까지 이동한 뒤 소멸한다는 뜻이다.
		if (moveLen == N) {
			Tornado(Start.first, Start.second, Direction, moveLen);
			break;
		}
	};

	cout << answer << "\n";

	return 0;
}

'BOJ > Gold' 카테고리의 다른 글

[BOJ/Gold 3] 백준 3425 고스택(C++)  (0) 2022.01.10
[BOJ/Gold 2] 백준 2136 개미(C++)  (0) 2022.01.10
[BOJ/Gold 4] 백준 2116 주사위 쌓기(C++)  (0) 2022.01.10
[BOJ/Gold 4] 백준 14499 주사위 굴리기(C++)  (0) 2022.01.10
[BOJ/Gold 4] 백준 17779 게리맨더링 2(C++)  (0) 2022.01.10

티스토리툴바