개요

간단한 탐색문제
문제를 보자마자 문제를 어떻게 풀어야하는지 감이 왔다.
단,문제를 풀면서 주의할 점이 몇부분 있는데 그 부분을 짚어보려고 한다.

문제분석

기후 온난화로 인하여,빙하가 녹는다.
빙하는 바다와 맞닿아 있는 방향의 개수만큼 높이가 낮아진다.
즉, 최대 4만큼 낮아질 수 있으며. 빙하는 독립적으로 녹기 때문에, 다른 빙하가 녹아서 바다가 된다고 해도 그 사실은 영향을 미치지 않는다.

다음과 같은 순서로 얼음이 녹는다.
우리가 구하고자 하는 값은 빙하가 두개로 나누어졌을때,그때까지 걸리는 시간이 얼마인가? 라는 것이다.

자 그럼 여기서 나올 수 있는 상황을 생각해보자.

가장 BEST CASE는 빙하가 모두 녹기 전에 빙하가 두개로 나누어지는 것이다. 이때는 그냥 걸린 시간을 리턴하는 것이다.

하지만 WORST CASE가 발생할 수 있다. 바로 빙하가 두개로 나누어지기도 전에 모든 빙하가 다 녹아버리는 문제이다.

이 문제는 이 부분을 놓칠 수 있기 때문에 본격적인 문제 풀이에 앞서 짚어보았다.

이제 어떻게 문제를 풀었는지 로직을 구상해보자.

문제의 로직은 단순하다. 빙하가 녹는다 -> 빙하가 두부분으로 나뉘었는지 확인한다.

나의 경우, Ice 클래스를 선언한 다음에 좌표와 함께 size를 같이 저장한다.

Ice를 담고있는 ArrayList를 데이터를 입력받는 동시에 담아준다. 0은 바다를 나타내기 때문에 주변에 바다가 얼마나 맞닿아 있는지 수를 센 다음,빙하의 현재 사이즈에서 맞닿은 수만큼 빼준다.

이때까지는 리스트에 해당 데이터를 담았기 때문에 지도에 담긴 값과는 독립적이다.

데이터를 적용했다면 적용한 데이터를 update 할 것이다.
나의 경우 리스트에 담긴 데이터를 통해 update를 하고있기 때문에, 0이 된 데이터에 대해서는 직접 지워주어야 한다.

여기에서 for문을 돌기 때문에 index 문제가 생길 수 있기 때문에 1을 빼주었다.

마지막으로 빙산이 두조각으로 나누어져있는지 확인하기 위해 bfs를 통해 탐색을 하였다.

여기에서 주의해야할 점은 빙산이 두조각으로 나누어져있는지 확인을 매번 해야하기 때문에,우리는 visited 배열을 매번 초기화해주어야한다 (사실 bfs 내부에서 해도된다)

bfs 탐색을 통해서 나올때마다 1을 리턴한다.

리턴하는 횟수가 2 이상일 경우 반복을 중지한다. 그렇지 않을 경우 시간을 늘려간다.
도중에 얼음이 모두 녹을 경우 = 리스트가 빌 경우 중단하며 걸리는 시간을 0으로 표시한다

이제 코드를 보자. 사실 내가 말한 내용이 모두 코드로 옮겨져있기 때문에.. 여기까지만 봐도 된다

문제풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * @since 2023/11/12
 **/
public class 빙산 {
	static class Ice{
		int x,y;
		int size;

		public Ice(int x, int y, int size) {
			this.x = x;
			this.y = y;
			this.size = size;
		}
	}
	static int N,M;
	static int[][] map;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static List<Ice> list;
	static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		list = new ArrayList<>();

		int time = 0; // 시간


		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<M;j++){
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] != 0) list.add(new Ice(i,j,map[i][j]));
			}
		}

		int lump = 0; // 덩어리 개수
		while(true){
			time++;
			for(Ice ice : list){
				int count = 0; // 주변 물의 개수
				for(int i=0;i<4;i++){
					int nx = ice.x + dx[i];
					int ny = ice.y + dy[i];

					if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
					if(map[nx][ny]== 0) count++;
				}
				if(ice.size > count) ice.size = ice.size - count;
				else ice.size = 0;
			}
			//얼음의 사이즈 지정해주기

			for(int i=0;i<list.size();i++){
				Ice ice = list.get(i);
				map[ice.x][ice.y] = ice.size; // 사이즈 재정의
				if(ice.size == 0) {
					list.remove(i--);
				}
			}

			if(list.isEmpty()) {
				time = 0; // 모든 얼음이 녹았을 경우
				break;
			}

			visited = new boolean[N][M];
			//매 분기마다 빙산의 높이가 달라지기 때문에 체크하기

			for(int i=0;i<N;i++){
				for(int j=0;j<M;j++){
					if(!visited[i][j] && map[i][j] > 0) {
						lump += bfs(i,j);
					}
				}
			}
			if(lump > 1) break;
			else {
				lump = 0;
			}

		}
		System.out.println(time);
	}

	static int bfs(int x,int y){
		Queue<int[]> que = new ArrayDeque<>();
		que.add(new int[]{x,y});
		visited[x][y] = true;

		while(!que.isEmpty()){
			int[] curr = que.poll();
			for(int i=0;i<4;i++){
				int nx = curr[0] + dx[i];
				int ny = curr[1] + dy[i];

				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if(visited[nx][ny]) continue; // 이미 방문한 적이 있을 경우
				if(map[nx][ny] == 0) continue; // 바다일경우
				visited[nx][ny] = true;
				que.add(new int[]{nx,ny});
			}
		}
		return 1;
	}
}