[BOJ]2636번 : 치즈

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

2636번: 치즈

알고리즘 분류

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

 

문제 파악

 

치즈의 모양이 0과 1로 주어지고 0은 공기층, 1은 치즈로 공기층과 맞닿아 있는 치즈는 1시간마다 녹아서 사라진다.

(단, 치즈 내부의 있는 공기층은 해당 되지 않음)

그렇다면 치즈가 모두 녹아지는 시간과 다 녹기 직전의 치즈 칸은 몇 칸인가?

 

문제 풀이

1. (0,0)으로 부터 너비 우선 탐색으로 외부 공기층을 모두 OutSide 배열에 true로 만든다. // FindOutSide 메서드

2. 치즈가 있는 칸에서 상,하,좌,우 중 공기층과 맞닿았다면 -1 처리를 해준다. // MeltDown 메서드

3. 치즈 칸을 -1 처리 해준 다음 남아 있는 치즈 칸의 개수를 세서 PrevCnt 변수에 담아 준다. //CountCheese

 

import java.util.*;

public class Main {
    
    static int N,M,time=0,prevcnt=0;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] cheese;
    static boolean[][] OutSide;
    static ArrayList<Point> Camera = new ArrayList<Point>();
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
    
        
        N = sc.nextInt();
        M = sc.nextInt();
        
        cheese = new int[N][M];
        OutSide = new boolean[N][M];
        
        for(int r = 0; r < N; r++)
        {
            for(int c = 0; c < M; c++)
            {
                cheese[r][c] = sc.nextInt();
                if(cheese[r][c] == 1) {
                    prevcnt++;
                }
            }
        }
        
        boolean init = true;
        while(init)
        {
            int x = 0;
            int y = 0;
            time++;            
            find:for(int row = 0; row<N;row++) {
                for(int col = 0; col<M;col++) {
                    if(cheese[row][col] == 0 && !OutSide[row][col]) {
                        x = row;
                        y = col;
                        break find;
                    }
                }
            }
            if(!FindOutSide(x,y)) 
            {
                init = false;
            }
            else {
                
                for(int row = 0; row<N;row++)
                {
                    Arrays.fill(OutSide[row], false);
                }
            }
        }
        
        System.out.println(time);
        System.out.println(prevcnt);
        sc.close();
    }


    private static boolean FindOutSide(int r, int c)
    {
        Queue<Point> q = new LinkedList<Point>();
        
        q.add(new Point(r,c));
        
        while(!q.isEmpty())
        {
            int size = q.size();
            
            for(int sz = 0; sz<size;sz++)
            {
                Point p = q.poll();
                
                int x = p.x;
                int y = p.y;
                
                for(int cycle = 0; cycle < 4; cycle++)
                {
                    int cx = x+dx[cycle];
                    int cy = y+dy[cycle];
                    
                    if(0<=cx && cx<N && 0<=cy && cy<M && !OutSide[cx][cy] && cheese[cx][cy] == 0) {
                        OutSide[cx][cy] = true;
                        q.add(new Point(cx,cy));
                    }
                }
            }
        }
        if(!MeltDown(OutSide)) {
            return false;
        }
        else {
            return true;
        }
    }

    private static boolean MeltDown(boolean[][] OutSide)
    {        
        for(int r = 0; r<N; r++)
        {
            for(int c = 0; c<M; c++)
            {
                if(cheese[r][c] == 1) {
                    if( 0<= r-1 && r+1<N && 0<=c-1 && c+1 <M) {
                        if(OutSide[r-1][c] || OutSide[r+1][c] || OutSide[r][c-1] || OutSide[r][c+1] ) {
                            cheese[r][c]--;
                        }
                    }
                }
            }
        }
        int cnt = CountCheese(cheese);        
        if(cnt!=0) {
            prevcnt = cnt;
        }        
        if(cnt ==0) {
            return false;
        }
        else {
            return true;
        }
    }

    private static int CountCheese(int[][] copyCheese)
    {
        int cnt = 0;
        for(int r = 0; r<N;r++)
        {
            for(int c =0; c<M;c++)
            {
                if(copyCheese[r][c] == 1) {
                    cnt++;
                }
            }
        }
        return cnt;
        
    }
}

class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}