[C++] 백준 2573번 빙산

DFS, BFS 문제입니다.

숫자는 빙산의 높이이며, 1년마다 주위에 빙산이 없는 수(0) 만큼 빙산이 녹습니다. (최대 4)
빙산이 두 개 이상의 덩이로 나누어지면 몇년이 걸렸는지를 출력하고,
전부녹아 없어지게되면 0을 출력합니다. (분리가 되지 않음)

1. DFS를 통해서 영역을 나누어서 몇덩이로 나누어져있는지 확인합니다.
   - DFS 탐색을 하지 않으면 빙산이 없는것이므로 0출력
   - 2번 이상 탐색하면 빙산이 여러 덩이인 것이므로 년도 출력 

2. 2차원 배열에 각 숫자의 상하좌우를 탐색해서 빙산을 녹입니다.

1, 2를 반복하여서 문제를 풀었습니다.

 

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

int n, m;
int countNum;
int countYear;
int map[310][310];
int chkMap[310][310];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };

void DFS(int a, int b)
{
	chkMap[a][b] = 0;
	for (int k = 0; k < 4; ++k) {
		int x = moveX[k] + b;
		int y = moveY[k] + a;
		if (chkMap[y][x] != 0) {
			DFS(y, x);
		}
	}
}

void copyMap(int paste[][310], int copy[][310])
{
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			paste[i][j] = copy[i][j];
		}
	}
}

void check(int a, int b) {
	for (int k = 0; k < 4; ++k) {
		int x = moveX[k] + b;
		int y = moveY[k] + a;
		if (map[y][x] == 0 && chkMap[a][b] > 0) {
			--chkMap[a][b];
		}
	}
}

int main(int argc, char *argv[])
{
	cin >> n;
	cin >> m;

	memset(map, 0, sizeof(map));
	memset(chkMap, 0, sizeof(chkMap));
	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> map[i][j];
			chkMap[i][j] = map[i][j];
		}
	}

	countYear = 0;
	while (1) {
		countNum = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				if (chkMap[i][j] != 0) {
					DFS(i, j);
					++countNum;
				}
			}
		}

		if (countNum == 0) {
			cout << "0" << endl;
			return 0;
		}
		else if (countNum > 1) {
			cout << countYear << endl;
			return 0;
		}

		copyMap(chkMap, map);
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				check(i, j);
			}
		}
		copyMap(map, chkMap);

		++countYear;
	}

	return 0;
}