[백준] 2636 치즈 - BFS JAVA

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

2636번: 치즈

 

문제풀이

일반 BFS 문제입니다. 이전에 풀었던  https://passionfruit200.tistory.com/380  백준 5547, 일루미네이션 문제와 매우 유사하다고 느꼈습니다.

치즈의 겉면을 확인하기 위하여

1. 치즈( 1 ) 를 BFS 시키는것이 아닌 치즈가 아닌곳 ( 0 )을 BFS 시킵니다.

2. 치즈가 아닌곳을 BFS 시키기 위해서 끝 부분은 무조건 0 으로 만들어주어야하기에 map = new int[N+2][M+2] 이런 형식으로 상하좌우를 한칸씩 늘려줍니다.

3. (0, 0) 에서 시작하여 치즈를 처음 만났다면 해당 치즈 구역은 무조건 바깥면입니다. 해당 치즈면을 99로 변화시켜줍니다.

4. Queue에 넣는 것은 치즈(1)이 아닌, Queue에는 치즈가 아닌곳( 0 ) 을 계속해서 넣어주어야 치즈의 안쪽면으로 들어가지 않습니다.

5. 그리고서 위의 1 ~ 4 번을 while문을 돌린다면 구할 수 있습니다.

 

하나 실수해서 시간이 좀 걸렸던 점은, meltflag = 99 인경우인데, 처음에 치즈가 녹기 시작한 곳을 2로 설정해둔곳도 있어서 2와 99가 맞지 않아 이후에는 meltflag로 변수를 통합시켜주었습니다.

 

또, 생각한대로 변수값들이 잘 들어가는지 확인하기 위해 출력문을 통해 확인해주었습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	public static int N, M;
	public static int[][] map;
	public static int[][] cheese;
	public static boolean[][] visited;
	public static int firstanswer=0;
	public static int secondanswer=0;
	public static int meltflag = 99;
    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+2][M+2];
    	visited = new boolean[N+2][M+2];
    	cheese = new int[N+2][M+2];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
//    	for(int i=0;i<=N+1;i++) {
//    		for(int j=0;j<=M+1;j++) {
//    			System.out.print(map[i][j]+" ");
//    		}
//    		System.out.println();
//    	}
    
    	boolean flag = false;
    	while(flag == false) {
        	visited = new boolean[N+2][M+2];
        	cheese = new int[N+2][M+2];
        	secondanswer = 0;
    		BFS(0, 0);
//    		System.out.println("======================================");
//        	for(int i=0;i<=N+1;i++) {
//        		for(int j=0;j<=M+1;j++) {
//        			System.out.print(map[i][j]+" ");
//        		}
//        		System.out.println();
//        	}
//    		System.out.println("*****************************");        	
//        	for(int i=0;i<=N+1;i++) {
//        		for(int j=0;j<=M+1;j++) {
//        			System.out.print(cheese[i][j]+" ");
//        		}
//        		System.out.println();
//        	}
//        
        	
    		// 1시간 뒤 모든 치즈를 녹입니다.
    		for(int i=0;i<=N+1;i++) {
    			for(int j=0;j<=M+1;j++) {
    				if(map[i][j] == meltflag) {
    					map[i][j] = 0;
    				}
    			}
    		}
    		
    		
    	
    		// 1시간 뒤 모든 치즈를 녹인후 아직도 치즈가 하나도 없는지 확인합니다.
    		// 치즈가 1개라도 있으면 아직 아닙니다.
    		
    		flag = true;
    		for(int i=0;i<=N+1;i++) {
    			for(int j=0;j<=M+1;j++) {
    				if(map[i][j] == 1) {
    					flag = false;
    					break;
    				}
    			}
    		}
    		
    		//만약 모든 치즈가 다 녹았다면, 녹기 한시간전에 남아있는 치즈조각이 저장되어있는
    		//cheese 배열에서 2의 개수를 가져오면 되겠습니다.
    		if( flag == true) {
        		for(int i=0;i<=N+1;i++) {
        			for(int j=0;j<=M+1;j++) {
        				if(cheese[i][j] == meltflag) {
        					secondanswer += 1; 
        				}
        			}
        		}
    		}
    		
    		firstanswer += 1;
    	}
    	
    	System.out.println(firstanswer);
    	System.out.println(secondanswer);			

    	
    }
    
    public static void BFS(int startx, int starty) {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	Queue<Node> q = new LinkedList<Node>();
    	q.offer(new Node(startx, starty));
    	visited[startx][starty] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if( nx < 0 || nx > N+1 || ny < 0 || ny > M+1) continue;
    			if(visited[nx][ny] == true) continue;
    			
    			// 빈 공간이라면 q에서 계속 탐색해야하니 넣어줍니다.
    			if(map[nx][ny] == 0) {
    				q.offer(new Node(nx, ny));
    				visited[nx][ny] = true;
    				
    			}
    			
    			
    			
    			// meltflag 라면 1시간뒤 녹는 것으로 생각합니다.
    			if(map[nx][ny] == 1) {
    				map[nx][ny] = meltflag;
    				cheese[nx][ny] = meltflag;
    			}
    		}
    	}
    	
    }
}

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