[백준 알고리즘] 백준 2636번 치즈 DFS 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 2636번 치즈 자바(Java)

1) 문제번호 : 2636번

 

2) 문제 출처

www.acmicpc.net/problem/2636

2636번: 치즈

 

2. 문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 치즈를 기준으로, 바깥과 안쪽의 공기를 나눠준다.

- 나눈 후에, 가장자리의 치즈를 구분하고, 치즈를 없애준다.

- 치즈를 없애고 구멍난 곳이 있으면 다시 구분해줘야 하는데, BFS로 하면, 따로 코드를 안짜도 되지만, DFS로 하면 2로 처리한 벽을 다시 0으로 처리하여 바깥과 안쪽 공기를 구분해줘야 한다.

 

7. 소스 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class cheese {
	private int r;
	private int c;
	
	cheese(int r, int c){
		this.r = r;
		this.c = c;
	}
}

public class Main {
	static int N; // 판 세로
	static int M; // 판 가로
	
	static int[][] board; // 판
	static boolean[][] check; //방문확인
	
	static int[] dr = {-1, 1, 0, 0}; //상하좌우
	static int[] dc = {0, 0, -1, 1}; //상하좌우
	
	static int time = 0; // 시간
	static int result = 0; // 치즈가 없어지기 1시간전 개수
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 판 세로
        M = sc.nextInt(); // 판 가로
        
        board = new int[N][M]; // 판
        
        
        //판 입력
        //1 : 치즈가 있는 칸, 0 : 치즈가 없는 칸
        for(int i=0;i<N;i++) {
        	for(int j=0;j<M;j++) {
        		board[i][j] = sc.nextInt();
        		//치즈 개수 구하기
        		if(board[i][j]==1) result++;
        	}
        }
        
        while(true) {
        	check = new boolean[N][M]; // 방문확인
        	//바깥과 내부 공기 구분
        	outair(0,0);
        	
        	//전체를 돌면서 치즈이면서 가장자리면 녹여
        	for(int i=0;i<N;i++) {
        		for(int j=0;j<M;j++) {
        			//치즈이면서 가장자리인 치즈면 없애자.
        			if(board[i][j]==1 && isEdgeCheese(i,j)) {
        				DFS(i,j);
        			}
        		}
        	}
        	
        	//-2로 되어 있는 곳 2로 바꿔주기
        	change();
        	
        	//다시 치즈 구멍난 곳을 확인하기 위해 2를 0으로 바꿔준다.
        	changeAir();
        	//1시간 증가
        	time++;
        	
        	//temp에 넣어서 temp가 0이 아니라면 result는 치즈의 개수가 되고, temp가 0이라면 멈춘다.
        	//그러면 result는 temp가 0이 되기 1시간 전 값
        	int temp = cheese();
        	if(temp!=0) result = cheese();
        	else break;
        }
        
        System.out.println(time);
        System.out.println(result);
        
    }
    
    //안쪽 공기랑 바깥 공기 구분하기
    public static void outair(int r, int c) {
    	check[r][c] = true;
    	board[r][c] = 2;
    	
    	for(int i=0;i<4;i++) {
    		int nr = r + dr[i];
    		int nc = c + dc[i];
    		
    		if(nr>=0 && nc>=0 && nr<N && nc < M) {
    			if(board[nr][nc]==0 && !check[nr][nc]) {
    				outair(nr,nc);
    			}
    		}
    	}
    }
    
    //board[i][j] 값이 2가 있으면 다시 0으로 바꿔줌 -> 안쪽이랑 바깥 공기 다시 구분하기 위해
    public static void changeAir() {
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(board[i][j]==2) board[i][j] = 0;
    		}
    	}
    }
    
    //치즈 개수 구하기
    public static int cheese() {
    	int count = 0;
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(board[i][j]==1) count++; 
    		}
    	}
    	return count;
    }
    
    //가장자리 치즈냐?
    public static boolean isEdgeCheese(int r, int c) {
    	//4방면 돌면서 바깥 공기가 있으면 true
    	for(int i=0;i<4;i++) {
    	    int nr = r + dr[i];
    		int nc = c + dc[i];
    		
    		if(board[nr][nc]==2) return true;
    	}
    	return false;
    }
    
    //가장자리 치즈 녹이기
    public static void DFS(int r, int c) {
    	check[r][c] = true;
    	board[r][c] = -2;
    	
    	for(int i=0;i<4;i++) {
    		int nr = r + dr[i];
    		int nc = c + dc[i];
    		
    		if(nr>=0 && nc>=0 && nr<N && nc < M) {
    			//치즈고, 방문 안했고, 가장자리 치즈면
    			if(board[nr][nc]==1 && !check[nr][nc] && isEdgeCheese(nr,nc)) {
    				DFS(nr,nc);
    			}
    		}
    	}
    }
    
    //치즈 녹인 곳을 다시 2로 만들기
    public static void change() {
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(board[i][j]==-2) board[i][j] = 2;
    		}
    	}
    }
}

 

---