[백준/JAVA] 2638번: 치즈

📖 문제

2638번: 치즈

 

 

 

 

💡  풀이 방식

• 구현, 시뮬레이션, BFS

필요 자료구조
- 4방향 탐색용 배열
- 외부 공기와 접촉한 수 저장용 2차원 int형 배열 air (-1: 외부 공기)
- 치즈 수

 

1. 가장자리는 무조건 공기이므로 (0,0)부터 BFS를 수행해 가장자리(-1)를 표시한다.

2. 치즈(=값이 1)인 곳에서  상하좌우 中 외부 공기(=값이 -1) 갯수를 센다.

3. 외부 공기와 2개 이상 접하면 치즈를 녹인다.

4. 치즈 갯수가 0개가 될 때까지 1-3 과정을 반복한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static int[][] map, air;
    static int cheeseCnt, time = 0;
    
    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)
                    cheeseCnt++;
            }
        }
        
        while(cheeseCnt != 0)
            melt();
        
        System.out.println(time);
    }
    
    private static void melt() {
        air = new int[N][M];    // 실내온도 공기와 접촉한 수 저장 배열
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        air[0][0] = -1; // -1 : 외부 공기
        
        while(!q.isEmpty()) { // 1. 바깥공기 영역 구하기
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny))    continue;
                
                if(map[nx][ny] == 1)    // 치즈라면, 탐색하려는 곳의 air 배열 값+1
                    air[nx][ny]++;
                
                if(map[nx][ny] == 0 && air[nx][ny] == 0) {    // 바깥공기 처리
                    air[nx][ny] = -1;
                    q.add(new int[] {nx, ny});
                }
            }
        }
        
        // 2. 적어도 2번 이상 외부 공기와 접촉해야 녹이기
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(air[i][j] >= 2) {
                    cheeseCnt--;
                    map[i][j] = 0;
                }
            }
        }
        
        time++;
    }
    
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- (DFS + BFS) int형 2차원 배열 1개, 방문 표시용 boolean형 2차원 배열 1개 사용하셨고,외부와 접촉한 공기는 2로 표시하셨다.

[백준 - Java] 2638번 : 치즈

 

---

💦 어려웠던 점

- 치즈 내부에 있는 공간은 어떻게 판별하지? 의 문제

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 풀이 참고

백준 2638 - 치즈 Java

백준 2638번 : 치즈 java

 

 

✔ 그림 설명 굿..

[백준] 2638번:치즈 (Java 자바)