언제나 처음처럼

[문제 링크]

 문제를 해결하기 위해 4가지 과정을 반복하였다.

1) iceMelt() 함수를 통해 빙산 주변에 있는 물의 수만큼 빙산을 녹인다.

2) 빙산이 2개 이상으로 나뉘어져 있는지 확인하기 위해 isSeparate() 함수를 정의하고, dfs() 를 통해 한 덩어리에 속한 빙산을 방문한다.

3)  만약 dfs()를 수행할 빙산이 없다면 모두 녹았다는 의미로 2를 반환한다.

4) dfs()를 수행했는데 아직 방문하지 않은 빙산이 있다면 분리되었다는 의미인 1을 반환하고, 모두 방문했다면 2개 이상으로 분리되지 않았다는 의미인 0을 반환한다.

isSeparate() 이 0을 반환했다면 위 과정을 다시 수행하고, 1을 반환했다면 누적한 시간을 출력, 2를 반환했다면 0을 출력한다.

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

struct Pos {
	int y;
	int x;
};

int N, M;
int board[300][300];
bool visited[300][300];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void dfs(Pos here) {
	visited[here.y][here.x] = true;

	for (int i = 0; i < 4; i++) {
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M)
			if (!visited[ny][nx] && board[ny][nx] != 0)
				dfs({ ny, nx });
	}
}

int isSeparate() {
	memset(visited, false, sizeof(visited));

	bool check = false;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] != 0 && !visited[i][j]) {
				if (!check) {
					dfs({ i, j });
					check = true;
				}
				else 
					return 1;
			}

	if (!check) 
		return 2;
	else 
		return 0;
}

void iceMelt() {
	int temp[300][300];
	memcpy(temp, board, sizeof(board));

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++) {
			if (temp[i][j] != 0) {
				int water = 0;
				for (int k = 0; k < 4; k++) {
					int ny = i + dy[k];
					int nx = j + dx[k];
					if (ny >= 0 && ny < N && nx >= 0 && nx < M)
						if (temp[ny][nx] == 0) water++;
				}
				board[i][j] -= water;
				if (board[i][j] < 0) board[i][j] = 0;
			}
		}
}

int solution() {
	int years = 0;
	int separate = isSeparate();

	while (separate == 0) {
		years++;
		iceMelt();
		separate = isSeparate();
	}

	if (separate == 1)
		return years;
	else
		return 0;
}

int main(void) {
	cin >> N >> M;

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

	cout << solution() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 165 day