[BOJ] 백준 2638 - 치즈 풀이

1. 문제

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

2638번: 치즈

2. 풀이

• 백준 골드 3에 해당하는 문제로 DFS로 해결했다.
• 입력을 받고 map을 구성하고 치즈의 개수를 세어 cheeseCnt에 저장한다.
• 주요 자료구조
  1. int cheeseCnt : 치즈 수
  2. boolean[][] visited : 외부 공기와 내부 공기를 구별할 boolean 배열
  3. Queue<Point> pointQueue : 치즈를 녹일 좌표가 들어있는 큐
• 이 문제의 핵심 포인트는 외부 공간 공기와 내부 공간의 공기를 구별하는 방법이다.
• 이는 문제에서 주어진 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다." 에서 얻을 수 있다.
  • 가장자리에는 치즈가 없으므로 (0, 0)에서 다음 노드가 0인 것만을 탐색하고, visited 배열을 true를 만들면서 DFS 돌면 외부 공기는 true, 내부 공기는 false가 된다.
  • 그 후 1인 부분에서 4방 탐색 DFS를 돌면서 visited 배열이 true인 개수가 2 이상인 위치만 pointQueue에 넣는다. 
  • 이때 pointQueue에 넣지 않고 바로 0으로 만들어 버리면, 다음 노드를 탐색할 때 visited 배열이 true인 개수가 더 카운트되는 문제가 발생한다.
  • 탐색이 끝났다면 pointQueue에서 하나씩 꺼내면서 치즈 개수를 하나 줄이고, 그 위치를 0으로 만든다.
  • 이 과정을 cheeseCnt가 0이 될 때까지 반복한다.
    
    
    

3. 소스코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N,M; // N : row, M : col
	static int[][] map; // 치즈 맵
	static int cheeseCnt = 0; // 치즈 수
	static boolean[][] visited;
	
    static int result = 0; // 치즈 수가 0이 될 때까지 걸린 시간
    
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    
    static class Point {
    	int x;
    	int y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
    }
    
    static Queue<Point> pointQueue; // 치즈를 녹일 좌표가 들어있는 큐

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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());
        		
        		if (map[i][j] == 1) {
        			cheeseCnt++;
        		}
        	}
        }

        // 반복문 시작
        while (true) {
        	if (cheeseCnt == 0) break;
        	
        	// visited 배열 초기화 및 큐 초기화
        	visited = new boolean[N][M];
        	pointQueue = new ArrayDeque<Main.Point>();
        	
        	// 외부 공기를 찾는 DFS
        	// 외부 : true, 내부 : false
        	cheeseDFS(0, 0);
        	
        	//4방 탐색으로 치즈가 외부 공기와 얼마나 접촉하는지 카운트
        	for (int i = 0; i < N; i++) {
        		for (int j = 0; j < M; j++) {
        			if (map[i][j] == 1 && cheeseCntMethod(i, j)) {
        				// 참이면 치즈가 녹는다는 얘기이므로
        				
        				pointQueue.add(new Point(i, j));
        			}
        		}
        	}
        	
        	// 리스트에 들어있는 만큼 치즈를 녹여준다.
        	while (!pointQueue.isEmpty()) {
        		Point poll = pointQueue.poll();
				map[poll.x][poll.y] = 0;
				cheeseCnt--;
			}
        	
        	// 다 끝났다면 1시간이 지남
        	result += 1;
        }
        
        // 결과 출력
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

	// 외부 공기 찾는 DFS
	private static void cheeseDFS(int x, int y) {
		visited[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int xf = x + dx[i];
			int yf = y + dy[i];
			
			if (isAvailable(xf, yf) && !visited[xf][yf] && map[xf][yf] == 0) {
				cheeseDFS(xf, yf);
			}
		}
	}
	
	// 배열의 범위를 넘는지 판단하는 함수
	private static boolean isAvailable(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}
	
	// 4방 탐색으로 치즈가 외부 공기와 얼마나 접촉하는지 카운트하는 함수
	private static boolean cheeseCntMethod(int x, int y) {
		int cnt = 0;
    	for (int i = 0; i < 4; i++) {
    		int xf = x + dx[i];
    		int yf = y + dy[i];
    		
    		// 외부 공기와 접촉한다면
    		if (map[xf][yf] == 0 && visited[xf][yf]) {
    			cnt++;
    		}
    	}
    	
    	return cnt >= 2 ? true : false;
	}
}

4. 배운점

• DFS 문제를 많이 풀어보자...
  
  
  

5. 점수

85/100