문제

• 
• 시간 제한: 1초
• 메모리 제한: 128MB

Problem Analsysis

문제의 핵심은, 외부 공기와 인접한 치즈를 먼저 녹인 후에, 그 뒤에 접근 가능한 내부 공기를 조사하는 것이다. 현재 시점에서의 외부 공기 Queue와 내부 공기(다음 시점의 외부 공기) Queue를 나누어서 순회하면 된다.

Algorithm

아래 논리로 BFS를 진행

• 인접 칸이 공기이면, 현재 시점의 외부 공기용 Queue에 추가
• 인접 칸이 치즈이면, 치즈의 접촉면을 더한다. 이때, 치즈가 녹으면, 해당 칸을 다음 외부용 Queue에 추가

• 현재 시점의 외부 공기 Queue가 끝날 때까지 반복
• 현재 시점의 외부 공기 Queue가 끝나면, 다음 시점 공기 Queue로 loop를 시작

Data Structure

• curQueue: 현재 시간에 접근 가능한, 외부 공기를 저장하는 Queue
• nextQueue: 다음 시간에 접근 가능한, 내부 공기를 저장하는 Queue
• board[N][M]: 치즈와 공기 현황을 저장, -1을 visited

결과

Other

시간 복잡도는 O(NM)이다.
기본적인 BFS에서 하나의 Queue를 사용하는 것과 다르게, 두 개의 Queue를 사용해야 한다는 점이 특징적이다.