[C++] 백준 2573 : 빙산

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

2573번: 빙산

백준 2573번 빙산 문제를 풀었다.

 

빙산을 BFS나 DFS로 탐색하는 문제다.

빙산이 두 덩어리 이상으로 분리되면 BFS나 DFS 탐색을 두 번 이상 할 것이다. 그러면 year를 출력해주면 된다.

만약 빙산이 동시에 사라져서 탐색을 하지 않는다면 0을 출력하면 된다.

 

빙산이 녹는 과정에서 주의할 것은 next_map배열에 빙산이 녹는 값을 넣어두고 일괄적으로 map배열을 갱신시켜줘야 한다. for문을 돌면서 한 점마다 녹는 값을 갱신하면 그 점이 0이 되었을 때 다른 점에게 영향을 미칠 수 있다.

 

테스트 케이스가 끝나면 항상 배열을 초기화 해준다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;
int map[300][300];
int next_map[300][300];
int visited[300][300];
int year;

void DFS(int x, int y) {
	visited[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (next_x >= 0 && next_x < n
			&& next_y >= 0 && next_y < m
			&& visited[next_x][next_y] == 0
			&& map[next_x][next_y] != 0) {
			visited[next_x][next_y] = 1;
			DFS(next_x, next_y);
		}
	}
}

int CheckSea(int x, int y) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (map[next_x][next_y] == 0)
			cnt++;
	}
	return cnt;
}

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

	while (1) {
		int land = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] != 0 && visited[i][j] == 0) {
					land++;
					DFS(i, j);
				}
			}
		}

		if (land >= 2) {
			cout << year;
			break;
		}
		if (land == 0) {
			cout << 0;
			break;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				next_map[i][j] = map[i][j] - CheckSea(i, j);
				if (next_map[i][j] < 0)
					next_map[i][j] = 0;
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = next_map[i][j];
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				next_map[i][j] = 0;
				visited[i][j] = 0;
			}
		}
		year++;
	}


	return 0;
}