2573_빙산[C++]

이 문제에는 빙산이 존재한다.

 

빙산은 일년마다 지구온난화로 인해 녹는다. 얼마나 녹느냐의 기준은 바닷물로부터 얼마나 둘러싸여있느냐에 따라 다르다.

 

그림1

그림 2는 그림 1의 일년뒤이다. 동, 서, 남, 북으로 바닷물의 닿아있는 정도에 따라 1년에 녹는 정도가 다르다.

 

출력은 빙산이 그림 3처럼 두조각으로 분리되는 최조의 시간(년)을 출력하는것이다.

 

문제풀이 방법

count를 이용해 bfs, dfs를 이용해 count >= 2이상 될시 두조각으로 분리된것으로 판단해 그 시간을 출력.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 301

int n, m; //y, x
int map[MAX][MAX];
int visit[MAX][MAX] = {0, };
int cnt = 0;
int maxH = 0;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void input()
{
	cin >> n >> m;
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> map[i][j];
			maxH = max(map[i][j], maxH);
		}
	}
}

void dfs(int y, int x)
{
	visit[y][x] += 1;
	for(int j = 0; j < 4; j++) {
		if(map[y + dy[j]][x + dx[j]] == 0 && map[y][x] != 0 && visit[y + dy[j]][x + dx[j]] < cnt + 1) {
			map[y][x] -= 1;
		}
	}	
	for(int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if(0 <= nx && nx < m && 0 <= ny && ny < n) {
			if(map[ny][nx] != 0 && visit[ny][nx] == cnt) {
				dfs(ny, nx);
			}
		}
	}
}

void print()
{
	cout << endl;
	for(int i = 0; i < n; i++) {
		for(int j =0 ; j < m; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool check()
{
	bool map_state = false;
	for(int i = 0; i < n; i++) {
		for(int j =0 ; j < m; j++) {
			if(map[i][j] >= 1)
				map_state = true;
		}
	}
	return map_state;
}

void solve()
{
	while(1) {
		int temp = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(map[i][j] != 0 && visit[i][j] == cnt) {
					dfs(i, j);
					temp += 1;
				}
			}
		}
		
		cnt += 1;
		
		if(temp >= 2) {
			cout << cnt - 1 << endl;
			return;
		}
		
		if(!check())
			break;
	}
	cout << 0 << endl;
	return;
}

int main()
{
	input();
	solve();
	
	return 0;
}