문제 링크

접근 방식

• arr를 계속 갱신하면서 가장 자리 판별하면 될듯
• 가장자리란? 상하좌우 중 한 곳이라도 치즈가 없으면 탈락!
• 가장자리인 곳은 2로 바꿔서.. 판별하면 되지 않을까
• 답은 Queue로 만들어서 size 출력하고 poll()하기
• 처음엔 어떤 알고리즘을 적용해야될지 감이 안 잡혀서 일단 for문을 엄청 돌렸다...

잘못 구현한 부분

• 메인 해결 방법이 외부 공기를 매 턴 BFS로 다시 찾아야 한다는 것이 핵심이었다.
• 가장자리인 곳을 2로 바꾸고 없애는 코드를 안 넣었었다..

time = 0
lastMelt = 0

while (true):
    외부공기 BFS()
    melt = 이번 턴에 녹일 치즈 리스트
    if melt.size == 0:
        break
    lastMelt = melt.size
    melt 치즈를 모두 arr에서 0으로 바꿈
    time++

왜 bfs?

• dfs로도 가능하다고 함
• 외부 공기에 닿은 영역만 색출해내야 하니까, 내부 공기쪽은 XX

// 빈 공간(0) → 계속 BFS 진행
if (arr[nx][ny] == 0) {
    visited[nx][ny] = true;
    q.add(new int[]{nx, ny});
}

// 치즈(1) → 외부공기와 닿았으므로 녹일 대상
else if (arr[nx][ny] == 1) {
    visited[nx][ny] = true;
    meltList.add(new int[]{nx, ny});
}

• 위 처럼 한번 닿았으면 visited=true 처리해서 더이상 깊게 안 들어가게 한다!

정답 코드

package algo.ct.M12;

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

public class BOJ_2636_치즈_G5 {
    static int n, m;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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());
        arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int time = 0;      // 총 시간
        int lastMelt = 0;  // 마지막에 녹은 치즈 개수

        while (true) {
        	// 매 턴마다 외부 공기 범위가 달라지니까
            visited = new boolean[n][m];

            // 이번 턴에 녹을 치즈들
            List<int[]> meltList = bfs();  

            if (meltList.size() == 0) {
                // 녹일 치즈가 없으면 종료
                break;
            }

            lastMelt = meltList.size();
            time++;

            // 실제로 치즈 녹이기
            for (int[] cur : meltList) {
                arr[cur[0]][cur[1]] = 0;
            }
        }

        System.out.println(time);
        System.out.println(lastMelt);
    }

    // 외부 공기를 BFS로 탐색하면서, 외부 공기와 닿은 치즈를 meltList에 담아 반환
    public static List<int[]> bfs() {
        Queue<int[]> q = new LinkedList<>();
        List<int[]> meltList = new ArrayList<>();

        // 항상 외부 공기는 (0,0)에서 시작
        q.add(new int[]{0, 0});
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

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

                // 범위 밖
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

                if (visited[nx][ny]) continue;

                // 빈 공간(0) → 계속 BFS 진행
                if (arr[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }

                // 치즈(1) → 외부공기와 닿았으므로 녹일 대상
                else if (arr[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    meltList.add(new int[]{nx, ny});
                }
            }
        }

        return meltList;
    }
}