[백준] 치즈 - Java

문제 링크

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

문제

문제 링크 참조

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

알고리즘: 구현, 시뮬레이션, BFS

풀이

공기에 닿는 순간 치즈는 1시간 후 녹게 된다.
비워져 있는 공간은 0으로 표시되지만, 그러한 공간이 모두 공기와 접촉한 것은 아니다.
예를 들면 사방이 치즈로 둘러싸이고 비워져 있는 공간은 공기와 접촉한 부분이 아니다.

그러면 공기와 접촉하는 부분만 찾아낼 수 있다면 문제는 쉽게 풀린다.

문제 설명을 보면 판의 가장자리는 치즈가 놓여 있지 않다. 즉 테두리는 무조건 공기와 접촉하는 부분이다. 그럼, 테두리(0, 0)부터 BFS를 이용해서 0이면 공기를 확산시키고 1이면 해당 치즈는 1시간 뒤 녹게 될 치즈이므로 구분해 놓는다.

위 방식으로 구현한다면 공기와 접촉한 치즈 부분을 BFS를 이용해서 쉽게 찾을 수 있다.

소스 코드

import java.util.*;
import java.io.*;
class Node {
    int x, y;
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, -1, 0, 1};
    static int W, H;
    static int[][] board;
    static int cheese = 0;
    static int answer_time = 0;
    static int answer_left = 0;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        H = sc.nextInt();
        W = sc.nextInt();
        board = new int[H][W]; //외부 공간
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                board[i][j] = sc.nextInt();
                if(board[i][j] == 1) cheese += 1;
            }
        }
        while(true) {
            if(cheese == 0) break;
            BFS();
        }
        System.out.println(answer_time);
        System.out.println(answer_left);
    }
    
    static void BFS() {
        Queue<Node> que = new LinkedList<>();
        boolean[][] visited = new boolean[H][W];
        que.add(new Node(0, 0));
        visited[0][0] = true;
        ArrayList<Node> c_list = new ArrayList<>();
        while(que.size() != 0) {
            Node n = que.poll();
            for(int i=0; i<4; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if(check_range(nx, ny) && !visited[ny][nx]) {
                    if(board[ny][nx] == 1) c_list.add(new Node(nx, ny));
                    else que.add(new Node(nx, ny));
                    visited[ny][nx] = true;
                }
            }
        }
        answer_time += 1;
        remove_cheese(c_list);
        if(cheese - c_list.size() == 0) answer_left = cheese;
        cheese -= c_list.size();
        
    }
    
    static void remove_cheese(ArrayList<Node> c_list) {
        for(int i=0; i<c_list.size(); i++) board[c_list.get(i).y][c_list.get(i).x] = 0;
    }
    
    static boolean check_range(int x, int y) {
        if((0 <= x && x <= W-1) && (0 <= y && y <= H-1)) return true;
        return false;
    }
}