[Unsolved][JAVA] 백준 2636 치즈

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

2636번: 치즈

 

 

1. 서론

 

엄청 전형적인 BFS 문제. 근데? 아이디어가 도저히 안 떠올라서 바로 인터넷을 찾아봤는데 그러고도 한참을 헤맨 문제이다.

 

2. 문제 풀이

 

2차원 배열에 치즈가 주어진다. 치즈가 있는 곳은 1, 빈 곳은 0이다.

배열에 주어진 값을 치즈 덩어리라고 가정할 때 치즈가 공기, 즉 0에 닿으면 닿은 부분은 녹아서 사라진다고 가정한다.

근데 포인트는 치즈를 한 덩이라고 보기 때문에 내부에 있는 0, 즉 치즈 안에 공기가 있는 부분은 녹아서 사라지지 않는다.

이때 1시간이 단위로 치즈가 녹는 것을 반복하는데 치즈가 다 녹는 시간과, 마지막으로 남은 치즈의 단위를 구하는 게 문제이다.

 

이 문제의 키포인트는 내부공기와 외부 공기를 어떻게 구분하느냐는 것이다.

내부, 외부 문제만 아니었다면 그냥 bfs 코드를 갈겼을 텐데 어떻게 구분하는지 도저히 생각이 안 날 것 같아서 바로 인터넷에 검색해봤다.

처음엔 한 블로그를 보면서 개념을 이해했다. 내부, 외부 공기를 나눠서 외부 공기에 닿은 부분만 제거하는 방법이었다. 근데 그 코드를 따라 해도 영 이해도 잘 안 되고 적용도 잘 안돼서 다른 블로그들도 뒤져본 결과 문제를 겨우 풀었다.

 

bfs로 배열을 돌면서 1인 부분이 있으면 그 부분만 2로 바꿔서 공기가 닿았다고 체크하고 큐에 넣지 않았다.

큐에 넣지 않으면 그 안으로 더 이상 탐색하지 않기 때문에 외부의 공기가 닿은 치즈 부분만 탐색할 수 있는 것이다.

그 외에 0인 부분은 큐에 넣어서 탐색을 계속했다.

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	static int[][] map;
	static int n, m, ans;
	
    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];
        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] == 1) ans++;
        	}
        }
        
        cheese();
    }
    
    public static void out() {// 공기 중에 치즈가 닿는 곳 표시
    	int[] dx = {0, 0, -1, 1}, dy = {1, -1, 0, 0};
    	Queue<Point> q = new LinkedList<Point>();
    	boolean[][] visit = new boolean[n][m];
   
    	visit[0][0] = true;
    	q.add(new Point(0, 0));
    	
    	while (!q.isEmpty()) { 
    		Point p = q.poll();
    		for (int k = 0; k < 4; k++) {
    			int nx = p.x + dx[k], ny = p.y + dy[k];
    			if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visit[nx][ny]) {
    				visit[nx][ny] = true;
    				if (map[nx][ny] == 1)
    					map[nx][ny] = 2;
    				if (map[nx][ny] == 0)
    					q.add(new Point(nx, ny));
    			}
    		}
    	}
    }
    
    public static void cheese() { //치즈 계산
    	int time = 0;
    	
    	while(true) {
    		time++;
    		
    		out();
    		
	    	for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (map[i][j] == 2) //치즈 녹임
						map[i][j] = 0;
			
    		if (check() == 0) break;
    		ans = check(); // 다 녹기 전의 값을 저장
    	}
    	
    	System.out.println(time + "\n" + ans);
    }
    
    public static int check() { //치즈가 다 녹았는지 체크
    	int cnt = 0;
    	
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < m; j++)
    			if (map[i][j] == 1)
    				cnt++;
 
    	return cnt;
    }
}

 

ans는 치즈의 수를 저장하는 값이다. 처음엔 그냥 0이라고 두고 코드를 돌렸는데 1시간만에 모든 치즈가 녹는 경우도 있을 수 있기 때문에 ans의 초기값은 모든 치즈의 개수를 저장해줬다. (이렇게 안 하고 그냥 돌리면 틀림)

 

값들을 입력받고 cheese 함수를 부른다. 거기서 치즈가 다 녹을 때까지 작업을 반복해준다.

out 함수는 치즈가 공기에 닿는 부분을 표시해주는 함수이다. 위의 설명처럼 1인 경우만 2로 표시를 바꿔주고 0일 때만 탐색하도록 했다.

그리고 방문처리를 통해 간 곳은 또 안가게 해 줬다. 이렇게 한 바퀴 돌며 치즈를 표시하고 2인 부분을 녹여주고 다 녹았는지 아닌지 체크한다. 다 녹지 않은 경우 위의 내용을 다시 반복하는 것이다. 다 녹은 경우는 반복문을 멈추고 값을 출력한다.

이때, 다 녹기 전의 치즈값을 출력해줘야 하기 때문에 break문 이후에 값을 저장한다.

 

조금만 응용해야 해도 바로 못푸는 내가 지겹다... ㅎ 코드는 또 간단해서 더 허무