🔗 문제

✏️ 풀이

오랜만에 문제 정리

[상태]

N x M 맵 (100 x 100)

[동작]

치즈 녹이기

간단하게 생각해낸 큰 틀은 아래와 같다.

while(totalCheese) // 모든 치즈가 녹을 때까지
{
    ++answer; // 걸린 시간
    melt() // 치즈를 녹여보자.
}

일단 "한 칸"씩 치즈가 녹으니 BFS가 적합한 알고리즘이라고 판단했다.

이제 세부조건 맞춰주기 전에 생각을 해보자.

맵의 상태가 2개이기 때문에 queue에 넣을 수 있는 것도 2개다.

(1) 치즈 기준으로 bfs를 돈다.

해당하는 치즈가 녹을 수 있는지 사방 탐색을 해야한다.

(2) 공기 기준으로 bfs를 돈다.

문제에서 아래 문장으로 공기 기준으로 bfs 돌리라고 힌트를 주고 있다. 이 문제가 골드 4라 그런지 친절하다. 👍

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다.

치즈가 녹으면 공기자리는 계속 생기므로, 공기를 넣는게 더 효율적이다.

가장 자리 아무거나 (0, 0) 먼저 큐에 넣어서 공기들을 다 visited 처리해주자.

자연스럽게 치즈로 둘러 쌓여 버린 공기는 치즈에 막혀서 만날 수 없다. -> 조건 (2) 충족 O

조건 (1)을 충족 시키기 위해서 counter[][]을 선언해주었다.

공기로 탐색을 하다가 치즈를 만나면 공기랑 만났다고 ++counter를 해준다.

그리고 제거 조건 counter == 2가 되면, 녹이고 다른 queue에 넣어준다.

치즈가 녹으면 그 자리는 다시 공기가 차지하게 되는 점을 이용해야 한다.

치즈가 녹은 위치가 다음번에 탐색할 공기들의 위치로 다시 재지정을 해준다.

이렇게 하면 다시 가장자리부터 치즈까지 닿기 위한 queue를 돌지 않아도 된다.

while(totalCheese)
{
        ++answer;
        air = melt(air); // 녹은 치즈의 위치를 담은 queue 반환
}