boj, 백준) 21610. 마법사 상어와 비바라기(C/C++)

1. 문제 링크

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

21610번: 마법사 상어와 비바라기

2. 문제 개요

N x N인 격자에서 비바라기를 연습하려고 한다. 격자의 ㅋ각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고 A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

 

맵의 위아래와 좌우는 연결된 것으로 본다.

 

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

 

규칙이 있는데, 규칙대로 M번 이동한 뒤 바구니에 들어있는 물의 양의 합을 구해보자.

 

3. 문제 힌트

주어진 규칙대로 천천히 실행하면 된다. 특별한 알고리즘이 필요한 것은 아니다.

 

구름 찾기 위해 매번 배열을 탐색하는 것은 비효율적이기 때문에 구름은 Queue에 담아주자.

 

이동하는 부분이 헷갈릴 수 있다.

맵이 원형으로 말려있다고 생각하면 되기 때문에, 나머지 연산을 통해서 이동을 구현해주어야 한다.

그런데 맵은 1부터 시작하기 때문에, bias를 -1을 두어 [1,N]범위를 [0,N-1]범위로 나머지 연산을 한 뒤 다시 [1,N]의 범위로 이동시켜주자.

 

4. 문제 풀이

(3)에 기술한 것 처럼 큰 알고리즘은 필요하지 않다.

 

이동하는 것을 생각해보자,

예를들어, 오른쪽 끝으로가면 왼쪽 끝에서 다시 나오게 된다.

그림 1

위 그림은 4에서 시작해서 5칸이동하여 2로 도착한 그림이다.

뭔가 맵을 넘어서 다시 시작점으로 간다.. 라고하면 나머지 연산을 바로 떠올려주면 된다.

그런데 나머지 연산은 N으로 나눌 경우 0~N-1의 범위를 갖는데, 맵은 1~N범위기 때문에 -1를 먼저 더해주고 처리를 한 뒤 마지막에 +1을 해주어야 한다.

 

x축 기준으로, 양의 방향으로 이동할 경우 다음과 같이 정의할 수 있다.

도착점 = (시작점 - 1 + 이동 거리 ) % N + 1

 

음의 방향으로 이동한다고 생각해보자.

 

그림 2

이번엔 2에서 시작해서 음의 방향(왼쪽)으로 5칸 이동해서 4에 도착한 경우이다.

위 식의 이동거리를 더해주는 것에서 빼주는 것만 다르다. 단, 나머지 연산을 하면 값의 범위가 [-N,-1]이 되는데, 이때 양수로 바꿔줘야한다. 이 부분은 밑의 수식을 코드로 옮길 때 처리해주면 된다.

도착점 = (시작점 - 1 - 이동 거리 ) % N + 1

 

 

이제 도착점을 구했다.

그럼 문제의 조건대로 비를 내려 물의 양을 1증가시켜주고, 구름을 제거한다.

이때 밑의 조건에 구름이 제거된 곳에서는 구름이 생길 수 없으므로 미리 어딘가에 구름이 제거 되었다는 것을 저장해주도록 하자.

 

그리고 나서, 

구름이 사라졌던 칸의 대각선 격자인 곳을 +1해준다. 이때는 맵이 원형인 것을 고려하지 않기 때문에 일반 BFS할 때 처럼 경계를 벗어나면 무시해주도록 하자.

5. 코드

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

struct COORD {
	COORD() {}
	COORD(int y_, int x_) :y(y_), x(x_) {}
	int y, x;
};

int map[51][51];
bool removed[51][51];

int n, m, ans;

constexpr int dx[] = { 0,-1,-1,0,1,1,1,0,-1 };
constexpr int dy[] = { 0,0,-1,-1,-1,0,1,1,1 };

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

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) 
			scanf("%d", &map[i][j]);
		
	queue<COORD> q, increased;
	q.push(COORD(n, 1));
	q.push(COORD(n, 2));
	q.push(COORD(n - 1, 1));
	q.push(COORD(n - 1, 2));

	while (m--)
	{
		int d, s;
		scanf("%d %d", &d, &s);
	
		while(!q.empty()){
			COORD cur = q.front(); q.pop();

			COORD next;
			next.y = cur.y + dy[d] * s - 1;
			next.x = cur.x + dx[d] * s - 1;

			next.y %= n;
			next.x %= n;

			next.y += n;
			next.x += n;

			next.y %= n;
			next.x %= n;

			next.y += 1;
			next.x += 1;

			++map[next.y][next.x];
			removed[next.y][next.x] = true;
			increased.push(next);
		}
		while (!increased.empty())
		{
			COORD cur = increased.front(); increased.pop();
			int increasement = 0;

			for (int dir = 2; dir <= 8; dir += 2)
			{
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 1 || ny <1 || nx >n || ny > n || map[ny][nx] == 0)
					continue;
				++increasement;
			}
			map[cur.y][cur.x] += increasement;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j){
				if (map[i][j] >= 2 && removed[i][j] == false){
					q.push(COORD(i, j));
					map[i][j] -= 2;
				}
				removed[i][j] = false;
			}
		}
	}
	for (int i = 1; i <= n; ++i) 
		for (int j = 1; j <= n; ++j) 
			ans += map[i][j];
	
	printf("%d", ans);


	return 0;
}

 

 

6. 결과