[구름 알고리즘 먼데이 챌린지] Week5 : 2. 모래섬

문제

바닷가에 놀러 간 구름이는 모래사장에서 모래를 쌓아서 모래섬을 만들었다. 구름이는 자신이 만든 모래섬 사이에 다리를 세우고 싶어한다. 다리를 그냥 만들 수도 있지만, 구름이는 서로 떨어진 섬과 섬을 이어줄 때 다리가 의미가 있다고 생각을 했다. 그래서 구름이는 모래사장에 물을 부어서 모래섬을 여러 개의 섬으로 나누고자 한다.

 

모래사장은 세로의 길이가 N, 가로의 길이가 M인 직사각형 모양의 땅이다. 모래사장을 1*1 크기로 나누었을 때, 가장 왼쪽 위부터 i번째 줄의 j번째 칸의 상태를 arr[i][j]라고 표현할 수 있다. 각 칸의 상태는 0또는 1중 하나이다.

●arr[i][j]의 값이 0이라면, 그 칸은 물에 가라앉은 칸임을 의미한다.

●arr[i][j]의 값이 1이라면, 그 칸은 모래가 쌓여있는 칸임을 의미한다.

매 분마다 모래가 쌓여있는 칸 중, 다음 조건에 해당하는 칸이 동시에 물에 가라앉게 된다.

●상하좌우로 인접한 칸 중, 물에 가라앉은 칸이 존재한다.

 

이때 하나의 모래섬은 다음 내용을 만족한다. 모래가 쌓여있는 칸 중, 상하좌우로 인접해있는 칸끼리는 이동할 수 있다. 단, 물에 가라앉은 칸이나 모래사장의 바깥으로는 이동할 수 없다. 그리고 어떤 칸에서 다른 칸으로 이동할 수 있는 경로가 존재한다면, 두 칸은 같은 모래섬에 속해있다.

 

구름이는 모래섬의 개수가 두 개 이상이 될 때, 다리를 건설하려고 한다. 구름이가 물을 부은 뒤 최소 몇 분 후에 다리를 건설 할 수 있는지 출력하시오. 단, 두 개 이상의 모래섬으로 나누어지지 않는 경우에는 -1을 출력하시오.

 

 

구름 알고리즘 먼데이 챌린지 4주차 2번 단풍나무 문제와 유사한 문제이다. 

 

크게 4가지 Phase를 구현하여 문제를 해결하였다.

1.물과 인접해 있는 모래 섬 좌표 구하기

2.물과 인접해 있는 모래 섬 물로 바꿔주기

3.모래 섬 개수 구하기

4.모래 섬 개수에 따라 다시 1번부터 진행할지 출력 후 종료 할지 판단. 

 

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

int n, m, board[101][101];
int dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1} };
vector<pair<int, int>> convert;

void check(int y, int x) {
	int ny, nx;
	for (int i = 0; i < 4; i++) {
		ny = y + dir[0][i];
		nx = x + dir[1][i];
		if (ny < 0 || ny > n - 1 || nx < 0 || nx > m - 1) continue;
		if (!board[ny][nx]) { //인접한 곳에 물이 있다면
			convert.push_back({ y, x });
			break;
		}
	}
}

void bfs(int y, int x, vector<vector<int>>& visited) {
	int cy, cx, ny, nx;
	visited[y][x] = 1;
	queue<pair<int, int>> q;
	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 (visited[ny][nx]) continue;
			if (!board[ny][nx]) continue;
			visited[ny][nx] = 1;
			q.push({ ny, nx });
		}
	}
}

int count_island() {
	int cnt = 0;
	vector<vector<int>> visited(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] && !visited[i][j]) {
				cnt++;
				bfs(i, j, visited);
			}
		}
	}
	return cnt;
}

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];

	int day = 0;
	while (true) {
		convert.clear();
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (board[i][j] == 1) check(i, j);
	
		for(const auto& [y, x] : convert) board[y][x] = 0;
		
		day++;
		int cnt = count_island();
		if (cnt >= 2) {
			cout << day; 
			return 0;
		}
		else if (cnt == 0) {
			cout << -1;
			return 0;
		}
	}

}