[백준]JAVA - 2636번: 치즈

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

2638번: 치즈

🔶 풀이

외부 공기와 접촉하고 있는 변이 2개 이상인 치즈는 1시간 뒤에 녹는다.

"몇 시간 뒤에 치즈가 다 녹아서 없어질까?"

 

처음엔 치즈를 기준으로 bfs를 돌릴 생각으로 풀다가 시간을 많이 소비했다.

치즈가 아닌 공기를 기준으로 bfs를 돌려야 정답을 구할 수 있는데 문제는 외부 공기와 내부 공기가 나누어져 있다.

 

(0, 0)부터 시작해서 bfs를 돌려준다.

내부 공기와 구분을 주기 위해서 외부 공기를 -1을 변경시켜 줬다.

public static void setMap() {
    Queue<Position> q = new LinkedList<>();
    boolean[][] visited = new boolean[N][M];
    q.add(new Position(0, 0));
    map[0][0] = -1;
		
    while (!q.isEmpty()) {
        Position now = q.poll();
			
        for (int i=0; i<4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
				
            if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || visited[nx][ny] || map[nx][ny] == 1) continue;
				
            // 외부공기(-1)로 변경
            q.add(new Position(nx, ny));
            map[nx][ny] = -1;
            visited[nx][ny] = true;
        }
    }
}

외부 공기를 변경시켜 줬으면 외부 공기와 접촉하고 있는 변이 2개 이상인 치즈를 찾아주면 된다.

찾아준 후에 deleteCheese 배열에 넣어줬고, 배열에 담긴 데이터들은 모두 0으로 변경시켜 준 후에 다시 위 내용을 반복했다.

 

바로 0으로 변경시켜주지 않고 deleteCheese 배열에 넣어준 이유는 "바로 0으로 만들어주게 되면 본래에 녹는 치즈가 아닌 것이 녹는 치즈가 된다"는 예외 조건 생기기 때문이다.

 

치즈가 다 녹아서 더 이상 deleteCheese 배열에 데이터가 없다면 반복문을 종료시켰다.

 

<최종코드>

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

public class Main {
    static int[][] map;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int N, M;
	
    public static class Position {
        int x;
        int y;
		
        public Position (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());
        
        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());
            }
        }
        
        int time = 0;
        ArrayList<Position> deleteCheese = new ArrayList<>();
        
        while (true) {        	
            deleteCheese.clear();
            setMap();
        	
            for (int i=0; i<N; i++) {
                for (int j=0; j<M; j++) {
                    if (map[i][j] == 1) {
                        if (checkDelCheese(i, j)) {
                            deleteCheese.add(new Position(i, j));
                        }
                    }
                }
            }
        	
            // 녹을 치즈가 없다면 반복문 종료
            if (deleteCheese.size() == 0) break;
    		
            // 한시간 증가
            time++;
        	
            // 녹은 치즈는 0으로 변경 (내부공기)
            for (Position cheese : deleteCheese) {
                map[cheese.x][cheese.y] = 0; 
            }
        }
        
        System.out.println(time);
    }
	
    public static boolean checkDelCheese(int x, int y) {
        int cnt = 0;
		
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
			
            if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1) continue;
			
            if (map[nx][ny] == -1) {
                cnt++;
            }
        }
		
        if (cnt > 1) return true;
        return false;
    }
	
    public static void setMap() {
        Queue<Position> q = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        q.add(new Position(0, 0));
        map[0][0] = -1;
		
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
				
                if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || visited[nx][ny] || map[nx][ny] == 1) continue;
				
                // 외부공기(-1)로 변경
                q.add(new Position(nx, ny));
                map[nx][ny] = -1;
                visited[nx][ny] = true;
            }
        }
    }
}