[Baekjoon]2573.빙산

2573.빙산

http://www.acmicpc.net/problem/2573

---

dfs로 푸는 문제였는데 문제의 조건 하나를 생각하지 못해서 계속 시간초과가 났다. 문제를 꼼꼼히 읽고 이해하는 연습이 더 필요할 것 같다.

접근은 다음과 같다.

 

1. 빙산을 녹인다.
2. dfs로 빙산의 개수를 카운트한다.
3. 카운트가 2이상이면 종료하고 아니면 1로 돌아가서 반복한다.

빙산을 녹이는 melting메소드를 짜면 나머지는 일반적인 탐색문제와 동일하다.

먼저 getAdjSea메소드로 각 칸이 인접한 0의 개수(바다와 인접한 면)를 세서 melt배열에 따로 저장한다. 

그 다음 원래 배열 map에서 배열melt에 저장된 값을 빼주고 만약에 그 값이 0보다 작으면 0으로 저장한다. 

이후에 map을 순회하며 빙산을 만나면 dfs를 실행하고 dfs를 빠져나올때 cntIce++로 빙산의 개수를 센다.

 

melting메소드를 빙산의 개수가 2개 이상이 되면 종료를 시키기 위해 while문을 이용하여 cntIce가 2이상이면 break를 하도록 했다.

여기서 한가지 빼먹어서 시간 초과가 났었다. 

 

빙산이 2개이상이 될때 while문을 빠져나오도록 했는데 이렇게 되면 위 그림처럼 빙산이 갈라지지 않고 동시에 다 녹아서 없어져버리는 경우에 while문을 빠져나오지 못하게 된다. 따라서 cntIce가 0이 될 때 break 하는 구문을 while문 마지막에 추가하여 해결했다.

 

private static void getAdjSea(int x, int y) {   // 바다에 인접한 면 카운트. 녹일 빙하량 저장. 
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
				continue;
			}
			if (map[nextY][nextX] == 0) {
				melt[y][x]++;
			}
		}
	}

 

빙산이 바다에 인접한 면의 개수를 세는 메소드로 빙산 상,하,좌,우를 탐색하여 0이 있으면 melt배열의 해당 인덱스값을 ++ 한다.

 

private static void melting() {
		while (true) {
			if (cntIce >= 2) {	// 빙하 개수가 2개 이상되면 break. 
				break;
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					getAdjSea(j, i);
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] != 0) {
						map[i][j] -= melt[i][j];
						if (map[i][j] < 0) {
							map[i][j] = 0;
						}
					}
				}
			}
			for (int[] row : melt) {			// melt 배열 초기화.
				Arrays.fill(row, 0);
			}
			for (boolean[] row : visited) {   	// visited 배열 초기화. 
				Arrays.fill(row, false);
			}
			cntIce = 0; 						// 빙하 개수 초기화. 
			
			explore();
			cntYear++;
			
			if (cntIce == 0) {	// 빙하가 다 녹아없어지면 break. 
				break;
			}
		}
	}

melting 메소드 전체코드이다.

<전체코드>