[백준/C++] 빙산_2573

📝 문제

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

💻 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

struct Ice {
	int row;
	int col;
	int ice;
};

int n, m;
int arr[301][301];
queue<Ice> q;
int visited[301][301];

int dr[] = { 0, 0, 1, -1 };
int dc[] = { 1, -1, 0, 0 };

void search() {
	// 빙산을 찾고 주위의 바다 갯수 저장
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			int cnt = 0;
			if (arr[i][j] >= 1) {	// 빙산 o
				for (int k = 0; k < 4; k++) {	// 빙산에서 4방향 탐색
					int nextRow = i + dr[k];
					int nextCol = j + dc[k];
					if (arr[nextRow][nextCol] == 0) cnt += 1;
				}
				q.push({ i, j, cnt });
			}
		}
	}
}

void dfs(int row, int col) {

	for (int k = 0; k < 4; k++) {	// 빙산에서 4방향 탐색
		int nextRow = row + dr[k];
		int nextCol = col + dc[k];
		if (visited[nextRow][nextCol] != 0) continue;
		if (arr[nextRow][nextCol] == 0) continue;
		visited[nextRow][nextCol] = 1;
		dfs(nextRow, nextCol);
	}

	return;
}

void bfs() {
	bool flag = false;
	search();
	int year = 0;
	while (!q.empty()) {

		// 갱신
		int len = q.size();
		for (int i = 0; i < len; i++) {
			Ice now = q.front();
			q.pop();
			if (arr[now.row][now.col] <= now.ice) {	// 바다가 더 크면 빙산 사라짐.
				arr[now.row][now.col] = 0;
			}
			else {
				arr[now.row][now.col] -= now.ice;
			}
			
		}

		year += 1;
		// 두 덩어리 이상 나눠졌는지 체크
		int cnt = 0;
		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (arr[i][j] >= 1 && visited[i][j] == 0) {
					visited[i][j] = 1;
					dfs(i, j);
					cnt += 1;
				}
			}
		}
		if (cnt >= 2) {
			flag = true;
			break;
		}
		for (int i = 0; i < 301; i++) {
			memset(visited[i], 0, sizeof(visited[i]));
		}

		// 큐 다시 설정
		search();
	}
	if (flag) cout << year;
	else cout << 0;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	
	bfs();
	

	return 0;
}

📌 해결방법

1. 모든 빙산을 찾고 주위의 바다 카운트
2. 모든 빙산이 동시에 업데이트 되도록 구현
3. dfs()로 빙산이 쪼개졌는지 확인
4. 빙산이 다 녹을때까지 1~3 반복

✔ 느낀 점

항상 2차원 배열 문제에서 모든 데이터를 동시에 갱신시켜주는 문제 유형을 못풀었는데 새벽감성에 취해 천천히 접근해서 풀이에 성공했다! 다음에는 new rice님이 저번에 어렵다고 한 문제랑 아기상어 풀어봐야겠다😁