이번에 풀어본 문제는
백준 2636번 치즈 입니다.

📕 문제 링크

❗️코드

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

class Point
{
    int x,y;

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

}
public class Main {
    static int N,M;
    static int [][] map;
    static boolean [][] visited;
    static Queue<Point> edges;
    static List<Point> next;
    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());

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

        edges = new LinkedList<>();
        visited = new boolean[N][M];
        next = new ArrayList<>();
        next.add(new Point(0,0));
        visited[0][0] = true;

        int hour = -1;
        int area = 0;
        while(!next.isEmpty())
        {
            area = next.size();
            edges.addAll(next);
            next = new ArrayList<>();
            findEdge();
            hour++;
        }
        //치즈가 없을경우 예외
        if(hour == 0) area = 0;
        System.out.printf("%d\n%d",hour,area);
    }
    static void findEdge()
    {
        while(!edges.isEmpty())
        {
            Point cur = edges.poll();

            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my]) continue;
                visited[mx][my] = true;
                // 치즈의 가장자리면 next , 공기중이면 현재 queue에 add;
                if(map[mx][my] > 0) next.add(new Point(mx,my));
                else edges.add(new Point(mx,my));
            }
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

주어진 입력에서, 공기와 맞닿는 치즈의 가장자리가 매 시간마다 녹는다는 조건입니다. 치즈가 모두 녹는데 걸리는 시간과 모두 녹기 직전 치즈의 크기를 출력하는 문제입니다.
먼저 가장자리를 구하는 함수 findEdge를 만들었습니다.
위 함수에서는 edges 큐에서 값을 꺼내면서, 사방으로 맞닿은 인덱스 중 치즈일 경우 next 리스트에 담아주는 작업을 수행합니다.
일반적인 bfs 유형과는 조금 다른 부분이, 가장자리를 찾았다면 더이상 bfs탐색에 관여하지 못하게 하기 위해서 별도의 List에 값을 담습니다. 이렇게 진행하게 되면 현재 상태에서 더 깊이 탐색을 하지 않고 정확히 치즈의 가장자리만 List에 담고 큐를 벗어날 수 있습니다.
findEdge함수가 종료되고 다시 while문으로 돌아오게 되면 시간을 1시간 증가시켜줍니다. 다음 반복의 진행여부는 next 리스트로 결정합니다. 만약 이전 findEdge함수에서 next 리스트에 값을 하나도 담지 못했다면, 더 이상 남은 치즈가 없다고 판단하고 반복문을 종료할 수 있습니다. 반대로 next에 값이 존재한다면 반복을 계속 진행하면 됩니다.

위 방법에서는 치즈가 하나도 존재하지 않을 경우 area = 1을 출력하기 때문에, 해당 경우만 예외적으로 조건문을 추가해주었습니다.

📜 후기

처음 치즈의 가장자리를 찾는 과정을 별도로 구성하면 좀 더 깔끔한 코드가 될 것 같은데, 비슷한 과정을 수행하는 함수를 두개 만드는 것도 그닥 맘에 들진 않아서 그냥 함수 하나로 해결해보았습니다.
가장자리를 치즈에서가 아닌 공기로부터 찾는다는 생각을 하게 되면 이후로는 어렵지 않은 문제라고 생각합니다.