[JAVA] BOJ(백준) - 빙산 - 2573

문제내용

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

2573번: 빙산

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

	2	4	5	3
	3		2	5	2
	7	6	2	4

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

		2	4	1
	1		1	5
	5	4	1	2

그림 2

			3
				4
	3	2

그림 3

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

---

문제 접근 방법

이문제는 BFS를 통해서 문제를 풀어낼 수 있는데 BFS를 몇번 돌려야되냐의 문제인것 같다. 즉, BFS 한번돌리기 = 1년이 흐른다 라고 생각하면 될것이다. 기본적으로 BFS를 알고 있다는 가정하에 내가 문제를 어떻게 접근했는지 설명 해보겠다.

 

로직

1. 시작점 구하기
   BFS를 돌리기 위해서는 처음에 큐에 넣어줄 초기 시작점(초기값)이 필요하다.
   따라서 입력받은 숫자 중에서 0이 아닌 숫자 한개를 찾아서 시작점으로 넣어주는 작업이 필요하다.
   
   
2. BFS 돌리기
   초기값을 시작으로해서 상하좌우를 살피고 0이 아닌 숫자를 큐에 담아준다.
   그리고 현재 탐색중인 값이 몇개의 0으로 둘러싸여 있는지 확인한뒤 0의 갯수만큼 현재 값에서 빼주는 작업을 한다.
   이때 현재 탐색중인 값의 상하좌우에 방문했던 점은 값이 0이더라도 제외시켜준다.(1년에 한번 녹는다는 생각을 갖고갈 필요가 있다.)
   
   
3. 빙하 덩어리가 2개 이상인지 체크하기
   2번까지 돌리고나서 빙하덩어리가 2개인지 아닌지 체크해주는 작업이 필요하다.
   이때는 빙하를 탐색하면서 0이 아닌 빙하이면서 방문배열에 탐색한적이 없는 빙하가 있을 경우 빙하 덩어리가 2개이상이라는 뜻이 된다.
   후에 2개덩어리 안나왔다면 1~3번을 반복해준다.
   
   
4. 끝까지 반복했는데 빙하가 두덩어리가 안될때
   이말은 곧 빙하가 처음부터 끝까지 한덩어리인 상태로 녹았다는 뜻이된다.
   이때는 시작점을 구하는 메서드가 모두 0을 가리킬때가 된다.

위의 과정을 통해 답을 구할수 있다.

코드를 보고 생각해보자.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr; //빙하
	static int n,m,ans; //arr배열의 크기와 정답
	static int[] dx = {-1, 1, 0, 0};//상하
	static int[] dy = {0, 0, -1, 1};//좌우
	static class Vertex{//큐에 넣어줄 객체
		int x;
		int y;
		public Vertex(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	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());
		ans = 0;
		arr = new int[n][m];
		
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<m; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//시작점 구하고 빙하 녹이고 두덩이 이상인지 체크하기를 반복.
		while(true) {
			int[] idx = init();//시작점 구하기(초기값)
			if(idx[0]==0 && idx[1]==0) {//초기값이 0이면 빙하 다녹음
                ans=0;//빙하 다녹을때까지 분리안돼서 0으로 재할당.
                break;
            }
			//빙하 녹이기(true이면 두덩이 이상된거임)
			if(meltIce(idx[0], idx[1])) break;
            ans++;//1년 증가
		}
		System.out.println(ans);
	}
	
	//초기값 구하기
	public static int[] init() {
		int[] idx = new int[2];
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(arr[i][j]!=0) {
					idx[0] = i;
					idx[1] = j;
					return idx;
				}
			}
		}
		return idx;
	}
	
	//BFS(1년치 빙하 녹이기)
	public static boolean meltIce(int xIdx, int yIdx) {
		Queue<Vertex> q = new LinkedList<Vertex>();
		boolean[][] check = new boolean[n][m]; //방문 배열
		
		q.add(new Vertex(xIdx, yIdx));
		check[xIdx][yIdx] = true;
		
		while(!q.isEmpty()) {
			Vertex curV = q.poll();
			
			//현재 점에서 상하좌우 탐색
			for(int i=0; i<4; i++) {
				int nextX = curV.x + dx[i];
				int nextY = curV.y + dy[i];
				
				//배열의 크기 안에 점이 있을때
				if(nextX>=0 && nextY>=0 && nextX<n && nextY<m) {
					//빙하가있고 방문안한 점일때
					if(arr[nextX][nextY]!=0 && !check[nextX][nextY]) {
						check[nextX][nextY] = true;
						q.add(new Vertex(nextX, nextY));
					}
					//현재 탐색점의 상하좌우점이 0이면서 방문안한 점일때, 현재점에서 1년치 녹이고 0보다 클때(사실이건 필요없는듯)
					if(arr[nextX][nextY]==0 && arr[curV.x][curV.y]-1>=0 && !check[nextX][nextY]) 
						arr[curV.x][curV.y]--;//현재점의 빙하 1년치 녹이기
				}
			}
		}//while
		
		//BFS 다돌고 빙하 탐색했는데 0이 아닌점에서 방문안한 빙하가 있는경우
		//빙하가 결국 두덩이 이상이라는 뜻이됨.
		for(int i=1; i<n-1; i++) {
			for(int j=1; j<m-1; j++) {
				if(arr[i][j]!=0 && !check[i][j]) return true;
			}
		}
		
		return false;
	}
}

 

---

마치며

BFS를 조금만 활용할줄 안다면 풀수 있는 문제라서 어렵진 않았다.