[C++] BOJ(백준) 2573 빙산

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

2573번: 빙산

 

BFS와 구현이 함께 있는 문제다.

문제의 알고리즘 분류를 보니 DFS로도 풀 수 있는 것 같다.

 

그림 문제처럼 덩어리를 파악하고 치즈 문제처럼 배열 전체에 BFS를 적용하는 횟수를 구해야 한다고 생각했다.

경험이 있는 문제들의 응용 문제 같아서 알고리즘이 쉽게 떠올랐다.

 

이 문제의 주의점은 올해(?) 녹은 빙산이 0이 되어 다른 빙산에 영향을 주면 안된다는 것이다.

이걸 해결하기 위해서는 visit 배열로 방문 여부를 체크했다.

 

main 에서 빙산을 찾으면 그 빙산과 이어진 빙산들에 대해 BFS를 실행했다.

즉, 빙산 덩어리를 체크할 수 있으므로 BFS 실행 횟수를 카운트 해 2이상이면 햇수를, 0이면 0을 출력했다.

 

BFS에서는 기본적인 조건을 통과하면 board의 값에 따라 다르게 실행했다.

빙산이라면 현재 빙산은 아무 영향을 받지 않으므로 큐에 삽입과 방문 여부만 저장해주고바다라면 현재 빙산의 높이를 1씩 줄였다.

 

착오없이 처음 생각한대로 성공했다.

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

int n, m;
int board[300][300];
int visit[300][300];
// 상하좌우 탐색을 위함
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

void BFS(int r, int c) {
	// <r, c>
	queue<pair<int, int>> q;

	visit[r][c] = 1;
	q.push({ r, c });
	
	// 큐가 빌 때까지 반복
	while (!q.empty()) {
		int curr = q.front().first;
		int curc = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int xx = curr + dx[i];
			int yy = curc + dy[i];

			// 범위를 벗어나거나 방문한 적 있으면 continue
			if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
			if (visit[xx][yy]) continue;

			// 주위가 바다면 빙산 높이 줄이기
			if (board[xx][yy] == 0)
				board[curr][curc] -= 1;

			// 주위가 빙산이면 큐에 삽입
			else {
				q.push({ xx, yy });
				visit[xx][yy] = 1;
			}

			// 빙산의 높이가 음수라면 0으로 설정
			if (board[curr][curc] < 0) board[curr][curc] = 0;
		}
	}
}

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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

	int cnt = 0;	// 햇수
	while (1) {
		memset(visit, false, sizeof(visit));
		int bfs = 0;	// 빙산 덩어리 수
		for (int i = 0 ; i < n;i++)
			for (int j = 0; j < m; j++) {
				if (board[i][j] && !visit[i][j]) {
					BFS(i ,j);
					bfs++;
				}
			}

		// 빙산이 두 덩이 이상으로 나눠졌다면 햇수 출력
		if (bfs > 1) {
			cout << cnt;
			return 0;
		}

		// 빙산이 모두 녹았다면 0 출력
		else if (bfs == 0) {
			cout << 0;
			return 0;
		}

		cnt++;
	}
}

main에서 반복문이 많이 사용되다 보니 시간이 좀 소요될 줄 알았는데 생각보단 양호하다.

 

한 번에 성공한 짜릿함🤗