[BOJ] 2636 치즈

접근법

치즈를 만났을 때부터 bfs를 도는 것이 아니라 (0,0)부터 bfs를 돌아야 치즈의 구멍을 만나지 않고 모서리만 그래프 탐색을 할 수 있다.
그래프 탐색 문제에서 중요한 것은 내가 원하는 좌표를 어떻게 순회할 수 있을지 찾는 것임을 잊지 말아야 한다.
그래서 치즈를 만나면 모서리임으로 visited 배열에 시간을 채워주고 큐에 추가하지 않는다.
그런 식으로 (0,0)부터 bfs를 계속 돌리다가 치즈를 공기로 바꿔준 횟수가 치즈의 횟수가 동일할 때 반복문에서 탈출했다.

visited 배열을 온전하게 사용할 수 없을 때 큐를 몇 번 돌리고 어떻게 탈출하게 할 것인지 파악하는 것도 중요하다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution2636 {

    static int n, m, ans, cnt;
    static int[][] map;
    static int[][] visited;
    static Queue<int[]> q = new LinkedList<>();
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    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][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) {
                    cnt++;
                }
            }
        }

        bfs();

        int cheese = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(visited[i][j] == ans) {
                    cheese++;
                }
            }
        }

        System.out.println(ans + " " + cheese);
    }

    static void bfs() {
        int cnt2 = 0;
        visited = new int[n][m];
        while(cnt != cnt2){
            ans++;
            q.add(new int[] {0, 0});
            boolean[][] visit = new boolean[n][m];
            while(!q.isEmpty()) {
                int[] xy = q.poll();
                int x = xy[0];
                int y = xy[1];
                visit[x][y] = true;
                for(int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(visit[nx][ny]) continue;
                    if(map[nx][ny] == 1) {
                        map[nx][ny] = 0;
                        visited[nx][ny] = ans;
                        visit[nx][ny] = true;
                        cnt2++;
                        continue;
                    }
                    visit[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }

}