[백준/C++] 2573번: 빙산 (지저분쓰한 DFS풀이)

 

쉬워보여서 금방 풀 줄 알았으나 나는 난독증에 걸려있었다... 빙하가 녹을 때 1년이 지나면 1씩 녹는 줄 알았는데 알고보니 주변에 빙하가 아닌 부분이 있는 만큼 녹는 것이었다. 그래서 좀 오래걸렸고 좀 지저분하게 푼 것 같다..

(반례모음) https://www.acmicpc.net/board/view/19033

 

입력 빙산:

1년 지난 빙산:

2년 지난 빙산:

내가 풀었던 과정을 설명해보면,

 

1) while문 내부에서

2) 방문했는지 확인하는 visit배열과 몇개의 빙하의 높이를 얼마 빼야되는지 계산하는 cnt_0배열을 초기화

3) 종료조건1: 만약 얼음이 없다면 0을 출력하고 break 

4) dfs함수를 통해 전체를 돌려서 몇덩이인지 센다.

5) 종료조건2: 만약 1덩이보다 많다면 년수 출력하고 break

6) 종료조건 어디도 안걸렸다면 년수를 1년추가하고 melt_cnt함수를 통해 cnt_0 배열에 각 자리에 녹는 빙하높이 저장

7) melt함수를 통해 cnt_0배열에 있는 빙하높이만큼을 빙하에서 빼줘서 빙하를 녹인다.

 

주의할 점은 처음에 빙하가 음수인 부분도 빙하가 없는 부분임으로 map[i][j]>0일때만 탐색해야한다.

#include<iostream>

using namespace std;

int row;
int col;
int map[300][300];
int visit[300][300];
int cnt_0[300][300];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };


bool isIce() {
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			if (map[i][j] > 0)return true; //얼음이 있으면 true
		}
	}
	return false; //얼음이 없으면 false
}

void melt_cnt(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= row || ny >= col)continue;
		if (map[nx][ny] <= 0)cnt_0[x][y]++;
	}
}

void melt() {
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			map[i][j] = map[i][j] - cnt_0[i][j];
		}
	}
}

void dfs(int x, int y) {

	int cnt_0 = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= row || ny >= col)continue;
		if (map[nx][ny] > 0 && visit[nx][ny] == 0) {
			visit[nx][ny] = 1;
			dfs(nx, ny);
		}
	}


}
int main() {


	//input part
	cin >> row >> col;
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) visit[i][j] = 1;
		}
	}


	//while문 시작
	int year = 0;
	while (1) {

		//초기화
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				//visit 배열 초기화
				visit[i][j] = 0;
				cnt_0[i][j] = 0;

			}
		}

		//종료조건1
		if (isIce() == false) {
			cout << "0";
			break;
		}


		int cnt = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (map[i][j] > 0 && visit[i][j] == 0) {
					visit[i][j] = 1;
					cnt++;
					dfs(i, j);
				}
			}
		}

		//종료조건2
		if (cnt > 1) {
			cout << year;
			break;
		}
		year++;

		
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (map[i][j] > 0) melt_cnt(i,j);
			}
		}

		melt();
		
	}

	return 0;
}