[백준] 2573-빙산(C++)

문제링크:https://www.acmicpc.net/problem/2573

2573번: 빙산

 

dfs 유형으로 분류되지만... 사실 단순 구현문제였습니다.

 

 

빙산이 몇개인지 확인하고, 빙산을 녹이고, 하는 과정을 구현하여 결과를 도출하면 됩니다.

 

알고리즘입니다.

• 1. 빙산이 몇조각인지 확인하기
• 2. 두조각 이상인지 확인하기
• 3. 얼음 녹이기 
• 4. 얼음이 다녹은지 확인

빙하가 몇조각인지 확인할 때에는 dfs 나 bfs중 편한것을 사용하시면 됩니다. 

 

#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0, result = 0;
int arr[300][300] = { 0 };
int temp[300][300] = { 0 };
int x_ar[4] = { 0,0,-1,1 };
int y_ar[4] = { 1,-1,0,0 };


void dfs(int yy,int xx,int cnt) {
	temp[yy][xx] = cnt; //temp에 표시 

	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < n&&x >= 0 && x < m)
			if (arr[y][x] && temp[y][x] == 0) 
				dfs(y, x, cnt);
			
	}
}
void melt_ice() {
	int melt = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) continue;
			melt = 0;
			for (int k = 0; k < 4; k++) {
				int y = i + y_ar[k];
				int x = j + x_ar[k];
				if (arr[y][x] == 0 && y >= 0 && y < n && x >= 0 && x < m)
					melt++;
			}

			if (arr[i][j] < melt) continue;
			else temp[i][j] = arr[i][j] - melt;
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			arr[i][j] = temp[i][j];
}


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

	while (1) {
		//1. 빙산이 몇조각인지 확인하기
		memset(temp, 0, sizeof(temp));
		int cnt = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (arr[i][j] && temp[i][j] == 0) {
					cnt++;
					dfs(i, j, cnt);
				}
		//2. 두조각 이상인지 확인하기 
		if (cnt >= 2) {
			cout << result << endl;
			return 0;
		}
		//3. 얼음 녹이기 
		memset(temp, 0, sizeof(temp));
		melt_ice();
		//4. 얼음이 다녹은지 확인
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (arr[i][j]) jud = true;

		if (jud == false) {
			cout << 0 << endl;
			return 0;
		}

		//카운트 증가
		result++;
	}
}