2573_빙산 => 꺼진 조건도 다시 보자

사용 알고리즘: bfs

사용 언어: java

 

 

처음에 59%쯤에서 시간 초과가 나길래 코드를 봤더니 아무 이상 없었음.

배열로 찾아가서 문제인가 싶어서 리스트도 만들어봤는데 계속 시간초과로 틀림.

아래는 시간초과 코드

package week21;

import java.util.*;
import java.io.*;

public class Main_bj_2573_빙산 {
	static int[][] map, cntIce;
	static int n,m;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		cntIce = new int[n][m];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++)
				map[i][j] = sc.nextInt();
		}
		//-------------------------------------
		
		int ans = 0;
		while(true) {
			//두 덩어리 이상인지 확인
			int dump = 0;
			boolean[][] visit = new boolean[n][m];
			//주위에 몇 개의 빙하가 있는지 개수 => cntIce
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					if(map[i][j] > 0 && !visit[i][j]) {
						dump++;
						if(dump > 1) 
							break;
						visit[i][j] = true;
						around_ice(visit, i,j);
					}
				}
			}
			if(dump > 1) 
				break;
			
			ans++; //1년 증가
			
			//녹이기
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					if(map[i][j] > 0) {
						map[i][j] = map[i][j] - cntIce[i][j] > 0 ? map[i][j] - cntIce[i][j] : 0;
					}
				}
			}
			
			//초기화
			for(int i=0; i<n; i++)
				Arrays.fill(cntIce[i], 0);
		}
		System.out.println(ans);
	}
	
	private static void around_ice(boolean[][] visit, int x, int y) {
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x,y});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			//주위 빙하 개수 구하기
			int ice = 0;
			for(int d=0; d<4; d++) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				
				
				if(nx>=0&&nx<n && ny>=0&&ny<m) {
					if(map[nx][ny] == 0)
						ice++;
					if(map[nx][ny] > 0 && !visit[nx][ny]) {
						visit[nx][ny] = true;
						q.add(new int[] {nx, ny});
					}
				}
//				if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
//				if(visit[nx][ny]) continue;
//				if(map[nx][ny] == 0) ice++;
//				if(map[nx][ny] != 0 && !visit[nx][ny]) {
//					visit[nx][ny] = true;
//					q.add(new int[] {nx, ny});
//				}
			}
			
			cntIce[cur[0]][cur[1]] = ice;
		}
	}

}

 

 

왜 안 되는지 계속 이유를 찾다가

만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

는 조건을 보게 됨....

package week21;

import java.util.*;
import java.io.*;

public class Main_bj_2573_빙산 {
	static int[][] map, cntIce;
	static List<int[]> floors = new ArrayList<>();
	static int n, m;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n][m];
		cntIce = new int[n][m];
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] > 0) 
					floors.add(new int[] {i, j});
			}
		}
		//-------------------------------------
		
		int ans = 0;
		while(true) {
			//두 덩어리 이상인지 확인
			int dump = 0;
			boolean[][] visit = new boolean[n][m];
			//주위에 몇 개의 빙하가 있는지 개수 => cntIce
			for(int[] floor : floors) {
				if(!visit[floor[0]][floor[1]]) {
					visit[floor[0]][floor[1]] = true;
					dump++;
					if(dump > 1) 
						break;
					around_ice(visit, floor[0], floor[1]);
				}
			}
			if(dump > 1) 
				break;
			if(dump == 0) {
				ans = 0;
				break;
			}
			
			ans++; //1년 증가
			
			//녹이기
			for(int i=floors.size()-1; i>=0; i--) {
				int x = floors.get(i)[0];
				int y = floors.get(i)[1];
				
				int melt = map[x][y] - cntIce[x][y];
				map[x][y] = melt > 0 ? melt : 0;
				
				if(map[x][y] == 0)
					floors.remove(i);
			}
			
			//초기화
			for(int i=0; i<n; i++)
				Arrays.fill(cntIce[i], 0);
		}
		System.out.println(ans);
	}
	
	private static void around_ice(boolean[][] visit, int x, int y) {
		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {x,y});
		
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			
			//주위 빙하 개수 구하기
			int ice = 0;
			for(int d=0; d<4; d++) {
				int nx = cur[0] + dx[d];
				int ny = cur[1] + dy[d];
				
				
				if(nx>=0&&nx<n && ny>=0&&ny<m) {
					if(map[nx][ny] == 0)
						ice++;
					if(map[nx][ny] > 0 && !visit[nx][ny]) {
						visit[nx][ny] = true;
						q.add(new int[] {nx, ny});
					}
				}
//				if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
//				if(visit[nx][ny]) continue;
//				if(map[nx][ny] == 0) ice++;
//				if(map[nx][ny] != 0 && !visit[nx][ny]) {
//					visit[nx][ny] = true;
//					q.add(new int[] {nx, ny});
//				}
			}
			
			cntIce[cur[0]][cur[1]] = ice;
		}
	}

}

if(dump == 0) {
ans = 0;
break;
}

=> 이 코드를 추가하여서 완전히 녹을 때까지 덩어리가 나뉘지 않을 때 처리를 해줌.

아마 59%쯤에서는 이러한 조건의 테스트케이스가 들어왔을 거고, dump가 2 이상 되는 경우가 없기 때문에 모든 빙하가 녹고서도 반복문을 무한루프했을 것임