[BOJ] 백준 2636 - 치즈 풀이

1. 문제

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

2636번: 치즈

2. 풀이

• 백준 2638 치즈 문제와 거의 똑같은 문제(https://www.acmicpc.net/problem/2638)
• 이 문제의 핵심 또한 가장 자리에는 치즈가 무조건 없으므로, 치즈가 없는 공간(공기 공간)이 외부 공기인지 내부 공기인지 파악하는 것이 중요하다.
  
  

주요 변수 및 자료구조

1. Queue<Point> pointQueue : 녹을 치즈의 좌표를 저장할 Queue
2. int cnt : while문을 돌 때마다 외부 공기의 개수를 저장할 변수
3. int size : 하루 전날, 남아있는 치즈의 개수를 저장할 변수

 

• while 무한 루프를 돌면서 다음과 같은 로직을 순서대로 수행한다.
  
  1. (0, 0)을 출발점으로 BFS를 돌면서 외부 치즈는 true, 외부 공기 및 치즈 공간은 true로 만든다. (visitedBFS() 함수)
  2. 외부 공기와 map의 크기가 같다면 break
  3. 외부 공기를 골랐다면, 전날 저장한 치즈의 갯수는 의미가 없으므로 0으로 초기화 한다.
  4. 치즈가 있는 공간에서 searchCheese() 함수를 실행하여 4방 탐색을 통해 하나라도 외부 공기를 만난다면(4방 중 하나라도 true를 만난다면) pointQueue에 좌표를 저장한다.
  5. pointQueue가 비어있을 때까지 꺼내면서 좌표에 존재하는 치즈를 녹인다.(0으로 만든다.)
  6. 이때, 녹인 치즈의 양은 size에 저장하고 하루(day)를 증가시킨다.
• 루프를 마치고 day와 size를 출력하면 정답
  
  

3. 소스 코드

package bfs;

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

public class Cheese2636 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;

    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 = new ArrayDeque<>();
    static int day = 0;
    static int cnt = 0;
    static int size = 0;

    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());
            }
        }

        while (true) {
            cnt = 0;

            // visited를 위한 BFS를 돌린다.
            visited = new boolean[N][M];
            visitedBFS();

            // 외부 공기와 맵의 크기가 같다면 break;
            if (cnt == N * M - 1) break;

            // 녹을 치즈를 고르는 함수
            size = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] == 1) {
                        searchCheese(i ,j);
                    }
                }
            }

            // 치즈를 녹인다.
            while(!pointQueue.isEmpty()) {
                Point poll = pointQueue.poll();
                map[poll.x][poll.y] = 0;
                size++;
            }

            day++;
        }

        bw.write(day + "\n" + size);
        bw.flush();
        bw.close();
        br.close();
    }

    private static void visitedBFS() {
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(0, 0));
        visited[0][0] = true;

        while (!q.isEmpty()) {
            Point poll = q.poll();

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (isAvailable(xf, yf) && !visited[xf][yf] && map[xf][yf] != 1) {
                    q.add(new Point(xf, yf));
                    visited[xf][yf] = true;
                    cnt++;
                }
            }
        }
    }

    private static void searchCheese(int x, int y) {
        boolean flag = false;

        for (int i = 0; i < 4; i++) {
            int xf = x + dx[i];
            int yf = y + dy[i];

            if (isAvailable(xf, yf) && visited[xf][yf]) {
                flag = true;
            }
        }

        if (flag) {
            pointQueue.add(new Point(x, y));
        }
    }

    // 범위에 넘는지 확인
    private static boolean isAvailable(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}

4. 점수

95 / 100