[백준/JAVA] 2636번: 치즈

📖 문제

2636번: 치즈

 

 

💡  풀이 방식

• BFS + 시뮬레이션

필요 자료구조
- 판 정보 저장할 2차원 int형 배열
- 2차원 boolean형 방문 표시 배열
- 남아있는 치즈조각이 놓여 있는 칸의 개수 저장하는 리스트

 

판에 치즈조각이 존재하는 동안 아래 과정을 반복한다.

① 방문 표시 배열을 초기화한다.

② (0,0)에서부터 BFS를 수행하며 경계선에 있는 모서리 칸들 = 공기(0)인 칸을 모두 방문 표시하러 간다. ((0,0)이 확실하게 공기인 칸이니까)

    → 이동 가능 조건 : 방문한 적 없는 치즈가 없는 칸(0)인 경우

 

③ 완전탐색을 통해 공기 중에 노출된 치즈를 녹이고, 판에 남은 치즈 갯수를 리스트에 저장한다.

    → 치즈 녹이는 조건 : 해당 칸이 치즈이고, 공중에 노출된 경우 = 주변에 방문 표시된 공기(0)가 있는 경우

④ 걸린 시간을 1만큼 증가한다.

 

 

마지막으로는 여태껏 걸린 시간과 저장한 판에 남은 치즈 갯수를 저장한 리스트의 맨 뒤에서 2번째 값 (= 모두 녹기 1시간 전 남아있는 치즈조각이 놓인 칸의 수)을 출력한다.

 

 

 

💥 유의사항

격자 범위를 벗어나지 않는지 확인하는 것은 기본 조건..!

 

 

🔺 코드

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[][] grid;
    static boolean[][] visited;
    
    static List<Integer> list = new ArrayList<>();  // 남은 치즈 칸 수 저장 리스트
    
    static int time, leftCnt;   // 녹아 없어지는 데 걸리는 시간 / 모두 녹기 1시간 전 남은 치즈 칸 수
    
    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());
        
        grid = new int[n][m];
        visited = new boolean[n][m];
        
        int tmp = 0;
        
        for(int i = 0 ; i < n ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < m ; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                if(grid[i][j] == 1) tmp++;
            }
        }
        list.add(tmp);
        
        while(true) {
            if(cntCheese() == 0) break;
            
            init();     // 1. 방문 배열 초기화
            bfs(0, 0);  // 2. (0,0)에서부터 bfs 통해 공기인 칸 모두 표시
            melt();     // 3. 공기 중에 놓인 치즈 녹이기
            time++;     // 시간 +1
        }
        
        System.out.println(time);
        System.out.println(list.get(list.size() - 2));    // 모두 녹기 1시간 전 남은 치즈조각 수 = 리스트의 뒤에서 2번째 값
    }
    
    // 판에서 치즈 수 세는 함수
    private static int cntCheese() {
        int cnt = 0;
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(grid[i][j] == 1) {
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
    
    // 방문 배열 초기화 함수
    private static void init() {
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
                visited[i][j] = false;
    }
 
    // 경계선 0 부분 모두 방문 표시하는 메소드 (BFS)
    private static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int dir = 0 ; dir < 4 ; dir++) {
                int nx = now[0] + dx[dir];
                int ny = now[1] + dy[dir];
                
                if(canGo(nx, ny)) {
                    q.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    // 치즈 녹이는 함수 : 본인이 치즈고, 주변에 값이 0인 방문한 칸이 존재한다면, 해당 칸 치즈는 녹이기
    private static void melt() {
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(grid[i][j] == 1 && airAround(i, j)) {
                    grid[i][j] = 0;
                }
            }
        }
        
        list.add(cntCheese());  // 판에 남은 치즈 갯수 리스트에 추가하기
    }
    
    // 공기에 노출되어 있는지 확인하는 함수 (격자 범위 내에 있고, 방문한 적 있는 0일 때)
    private static boolean airAround(int x, int y) {
        for(int dir = 0 ; dir < 4 ; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(inRange(nx, ny) && grid[nx][ny] == 0 && visited[nx][ny]) {
                return true;
            }
        }
        
        return false;
    }
    
    // 격자 범위 내에 있고, 방문한 적 없는 치즈가 없는 칸이라면 방문 가능
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && !visited[x][y] && grid[x][y] == 0);
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < n && 0 <= y && y < m);
    }
}
 

 

 

➕ 다른 풀이 방식

1) 따로 녹이는 메소드와 갯수 저장 리스트를 두지 않고, (0,0)에서 BFS 수행하면서 다음 이동할 칸이 치즈라면 바로 녹이는 식으로 진행하셨다. 나도 담엔 이렇게 풀어야지 ✅

[백준]2636: 치즈 - JAVA

 

 

2) DFS 수행

[BOJ] 백준 2636번 : 치즈 (JAVA)

---

💦 어려웠던 점

40분 소요,,

아 한 방에 맞췄다..😭😭

감사합니다..

 

 

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

 

 

(+ 240303 2회독)

28분 소요! (15236KB, 160ms)

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;
    
    static int time = 0;
    static List<Integer> list = new ArrayList<>();
    
    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());
            }
        }
        
        while(true) {
            if(!cheeseExists()) break;
                
            time++;
            melt();
        }
        
        System.out.println(time);
        System.out.println(list.get(list.size() - 1));
    }
    
    // 치즈가 존재하는지 확인하는 함수
    private static boolean cheeseExists() {
        boolean exists = false;
        int cnt = 0;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 1) {
                    exists = true;
                    cnt++;
                }
            }
        }
        
        if(cnt != 0)    list.add(cnt);
        
        return exists;
    }
    
    // [BFS] 치즈 녹이기
    private static void melt() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0, 0});
        
        // 방문 배열 매번 초기화하기
        boolean[][] visited = new boolean[N][M];
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            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) || visited[nx][ny])    continue;
                
                if(map[nx][ny] == 0) {    // 치즈가 아닌 칸의 경우, 방문 처리하고 큐에추가
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
                else if(map[nx][ny] == 1) {    // 치즈인 칸의 경우, 방문 처리하고 녹이기
                    visited[nx][ny ] = true;
                    map[nx][ny] = 0;
                }
            }
        }
    }
    
    // 격자 범위 벗어나는지 확인하는 함수
    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}
 

 

지난 번에 인상깊게 본(?) 풀이처럼 진행했다.

- 치즈가 존재한다면, 현재 존재하는 치즈 갯수를 리스트에 저장하도록 했다. → 그냥 치즈 갯수 변수로 저장해서 써도 되었는디..

- (0,0)부터 bfs를 수행하면서 해당 칸이 방문한 적 없는 치즈가 있는 칸(1)이라면, 방문 표시하고, 0으로 바꿔 치즈를 녹여줬다.