[구름] 모래성

문제

바닷가에 놀러 간 구름이는 모래사장에서 모래 섬을 만들었다. 구르미는 자신이 만든 모래 섬에 다리를 세우고 싶어한다.

다리를 그냥 만들 수 있지만, 다리는 섬과 섬을 이어줄 때 그 의미가 있다고 생각을 했다. 구르미는 섬을 만들기 위해서 모래사장에 물을 붇기로 한다. 모래 섬은 주변에 물이 있으면 무너져 내린다.

 

현재 모래사장은 세로의 길이가 n, 가로의 길이가 m 크기이다. 모래사장을 1*1크기로 나누었을 때,

가장 왼쪽 위부터 i번째 줄의 j번째 칸을 arr[i][j]라고 표현할 수 있다.

 

arr[i][j]의 값이 0이라면 이미 물에 가라앉았다는 의미이다. arr[i][j]이 양의 정수라면, 현재 위치의 모래의 고도이다. 모래는 주변의 물의 양에 따라서 매분마다 무너져 내린다.

arr[i][j]의 상태가 모래라면, 모래사장 안에서

arr[i-1][j]. arr[i+1][j], arr[i][j-1], arr[i][j+1]의 상태에 영향을 받는다. 4곳의 상태 중 하나라도 물이 있다면, 물인 상태의 개수만큼 모래는 무너져 내린다. 모래의 고도는 0이하로 떨어지지 않으며, 4곳의 상태가 모두 모래라면 모래의 고도는 낮아지지 않는다.

 

매 분마다 위의 과정이 반복된다. 위의 과정을 통해서 모래 섬이 2개 이상의 섬으로 나누어지면 다리를 건설할 수 있는 상태이다. 구름이가 물을 부운 뒤 몇분이 지난 뒤에 다리를 건설할 수 있는지 출력하시오. 단, 다리를 건설할 수 업서나, 이미 나누어져 있다면 0을 출력하시오.

---

입력

첫째 줄에 모래사장의 크기 n, m (1 <= n, m <= 1,000)이 공백을 두고 주어진다.

 

둘째 줄부터 n줄에 걸쳐서 현재 모래사장의 상태가 주어진다. i+1번째 줄의 j번째 수는 arr[i][j]의 값이며, 각 숫자는 공백을 두고 주어진다. arr[i][j]은 0이상 100이하의 정수이다.

---

문제를 읽고 시물레이션, 구현 문제로 판단했다.

문제를 토대로 예시2)를 살펴보며 더 정확하게 이해해보자.

0분

5 2 0

0 7 0

0 0 0

5, 2, 7의 섬이 모두 이어져 있기 때문에 초기 상태부터 이미 2개 이상의 섬으로 나누어져 있진 않다.

따라서, 각 모래 섬의 고도를 인접한 4방향의 상태(물인지, 모래인지)에 맞게 낮춰주는 작업을 수행하도록 하자.

1분

4 1 0

0 4 0

0 0 0

1분 후 모래 섬들의 고도를 조건에 맞게 낮춰준 상태이며, 여전히 하나의 모래 섬으로 이어져 있다.

따라서, 다시 한번 위 작업을 수행해 주자.

2분

3 0 0

0 1 0

0 0 0

2분이 지났을 때 2개 이상의 섬으로 나누어지므로 정답은 2(분)를 출력하면 되는 것이다.

 

처음엔 모래 섬의 개수를 확인하는 함수와 모래 섬들의 고도를 낮춰주는 함수를 작성하여 문제를 해결하고자 했다.

하지만, 모래 섬의 개수를 확인하는 것과 모래 섬들의 고도를 낮춰주는 작업을 하나의 함수로 한꺼번에 처리할 수 있을거 같아 중간에 로직을 수정하였다.

 

구현한 소스 코드는 아래와 같다.

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

int n, m, minute, dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1} };
vector<vector<int>> board(1001, vector<int>(1001, 0));
vector<vector<int>> temp(1001, vector<int>(1001, 0));

void bfs(int y, int x, vector<vector<int>>& visited) {
	int cy, cx, ny, nx;
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (!q.empty()) {
		cy = q.front().first;
		cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			ny = cy + dir[0][i];
			nx = cx + dir[1][i];
			if (ny < 0 || ny > n - 1 || nx < 0 || nx > m - 1) continue;
			if (!board[ny][nx] && temp[cy][cx]) {
				temp[cy][cx]--;
				continue;
			}
			if (visited[ny][nx]) continue;
			visited[ny][nx] = 1;
			q.push({ ny, nx });
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) cin >> board[i][j];

	while (true) {
		vector<vector<int>> visited(n + 1, vector<int>(m + 1, 0));
		temp = board;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (visited[i][j]) continue;
				if (!board[i][j]) continue;
				bfs(i, j, visited);
				cnt++;
			}
		}
		if (cnt >= 2) { cout << minute; return 0;}
		else if (cnt == 0) { cout << 0; return 0;}
		minute++;
		board = temp; //board에 고도 값 변경을 마지막에 동시에 처리
	}

	return 0;
}

 

1.초기 값 입력받기

먼저, 모래사장의 크기 n, m과 초기 모래사장의 상태를 board에 입력받는다.

 

2.섬 개수 세기

모래 사장의 모든 좌표의 방문 여부를 판단하는 visited배열을 생성하고

이중 for문으로 모든 좌표 중 방문한적 없는 모래섬 좌표들만 bfs를 수행하자. 이렇게 하면 이어진 섬들을 하나의 섬으로 취급하여 섬의 개수를 구할 수 있다.   

 

3.temp

모래 섬들의 고도를 낮춰주는 처리는 동시에 이루어져야 한다.

예를들어, 위 예시의 1분이 지난상태에서 다시 1분이 지나 고도를 낮춰는 상황을 생각해보자.

이때, 동시에 고도를 낮춰주지 않고  4(0,0), 1, 4(1,1) 순서로 고도를 낮춰주는 경우 어떤 문제가 발생할 수 있는지 생각해 봐야한다.

1분

4 1 0

0 4 0

0 0 0

 

3 1 0

0 4 0

0 0 0

 

3 0 0

0 4 0

0 0 0 여기 까지는 아무 문제 없지만

 

3 0 0

0 0 0

0 0 0 (1,1)의 섬의 고도를 낮춰주는 과정에서 1이 아니라 0으로 변경되는 것을 알 수 있다.

즉, 고도 감소를 동시에 처리해 주지 않으면 이전에 먼저 처리된 상황에 의해 다른 섬들이 영향을 받아 문제 조건과 다르게 동작 할 수 있는 것이다. 

따라서, 현재 모래 사장 상태 board를 temp에 복사 해준 뒤

인접한 좌표의 상태는 board를 기준으로 확인하고 변경사항은 temp에 저장 해 주는 것이다. 

이후 모든 고도감소를 temp에 저장 했다면 마지막에 board = temp로 board에 변경 사항을 복사해 주면 기준인 board는 현재 상태이고 변경은 마지막에 한번에 이루어 지므로 모래 섬들이 서로에게 잘못된 영향을 미치는 것을 막을 수 있다.

 

4.bfs

if (!board[ny][nx] && temp[cy][cx]) {temp[cy][cx]--;continue;}

위 조건문을 제외하고 전형적인 bfs와 로직과 동일하다.

if문은 문제 조건에 따라 모래섬의 고도를 0이하로 낮출 필요가 없기 때문에 효율성을 위해 추가해 주었다.