[백준 BOJ 2573 glod4 - 빙산] DFS C++

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

2573번: 빙산

기본적인 dfs 만 구현할 줄 안다면 풀 수 있는 문제이다. 

 

1년씩 지나면서 빙산이 녹을 때, 처음으로 덩어리가 두개 이상이 되는 최초의 시간을 출력한다.

 

첫번째

상하좌우 4방향 중에서 비어있는 경우(0인 경우)의 개수만큼 빼준다.

여기서 주의해야 할 점은, 현재 상태를 기준으로 보고 빼줘야 한다. (동시에 녹는다고 본다)

표시한 부분에서 2-2 = 0 이 되어도, 4부분을 볼 때는 왼쪽은 0 이 아니라 2인 것이다. 

두번째

 

여러 번 틀렸습니다가 떴었다. 아마 놓친 부분이 있다면 이 중 하나일 확률이 높다.

 

1. 처음부터 덩어리가 2개 이상으로 분리되어 있다면 0을 출력해야 한다.

2. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.(문제에서 주어진 예외처리)

3. dfs로 돌면서 덩어리 개수를 셀 때, 대각선으로 붙어있어도 한 덩어리로 취급했다. 상하좌우만 연결된 것으로 봐야한다..

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>
#include <string.h>
#include <iostream>
#include <map>

using namespace std;

int N, M;
int arr[300][300];
int zero[300][300];
int visit[300][300];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int getcount(int x, int y) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (arr[nx][ny] == 0) cnt++;
	}
	return cnt;
}
int range(int x, int y) {
	if (x >= 0 && y >= 0 && x < N && y < M && !visit[x][y])
		return 1;
	return 0;
}
void dfs(int x, int y) {
	visit[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if ( range(nx, ny) && arr[nx][ny] > 0) {
			dfs(nx, ny);
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	int first = 0; //처음부터 이미 두 덩어리 이상이라면 0을 출력 ** 
	for (int i = 1; i <= N - 2; i++) {
		for (int j = 1; j <= M - 2; j++) {
			if (arr[i][j] != 0 && visit[i][j] == 0) {
				dfs(i, j);
				first++;
			}
		}
	}
	if (first >= 2) {
		cout << 0;
		return 0;
	}

	int years = 0;
	while (true) {
		memset(visit, 0, sizeof(visit));
		memset(zero, 0, sizeof(visit));
		for (int i = 1; i <= N-2; i++) {
			for (int j = 1; j <= M-2; j++) {
				if (arr[i][j] != 0) {
					zero[i][j] = getcount(i, j);
				}
			}
		}
		for (int i = 1; i <= N-2; i++) {
			for (int j = 1; j <= M-2; j++) {
				arr[i][j] -= zero[i][j];
				if (arr[i][j] < 0) arr[i][j] = 0;
			}
		}
		int numzero = 0; //numzero가 0 이라면 모든 수가 0 -> 다녹음
		for (int i = 1; i <= N - 2; i++) {
			for (int j = 1; j <= M - 2; j++) {
				if (arr[i][j] != 0) numzero++;
			}
		}
		int island = 0; //dfs로 덩어리 개수 세기
		for (int i = 1; i <= N-2; i++) {
			for (int j = 1; j <= M-2; j++) {
				if (arr[i][j] != 0 && visit[i][j] == 0) {
					dfs(i, j);
					island++;
				}
			}
		}
		years++;
		if (island >= 2) break; //두개 이상일 경우 year출력
		if (island < 2 && numzero == 0) {//모두 녹았는데 덩어리가 2개이상으로 분리 안된경우 0출력
			cout << 0;
			return 0;
		}
	}
	cout << years;
}

자꾸 틀려서 뭘 추가하다 보니 코드가 너무 더러워졌다 ㅎㅎ... 

다음에 다시 풀 때는 더 깔끔하게 짜보겠다!!