그래프와 순회. [7576]

[1. 문제 설명]

창고 내 한 격자에 토마토 한개를 보관 할 수 있다.

익은 토마토 하나는 인접한 곳에 익지 않은 토마토를 익게 할 수 있다.

 

창고 내 모든 토마토가 익는데 걸리는 최소 일수를 구하도록 하고,

모든 토마토가 익을 수 없는 경우 -1 을 출력 한다.

 

 

 

[2. 풀이 접근]

잘못 된 접근

• 아직 방문하지 않은 좌표 중, 익은 토마토 위치에서 bfs 를 시작,
  이 과정을 마지막 좌표까지 반복
  => 처음에 익은 상태에 모든 토마토에서 이 과정이 동시에 시작되어야 함.
  => 위 방법은 잘못된 계산을 유도할 수 있음.
       아래와 같이 A 와 B 가 모두 익은 상태인 경우, x3 가 익는 시점은 3 이 아니라 1 이다.
  => A - x1 - x2 - x3 - B

올바른 접근

1. 최초 익은 토마토의 위치를 모두 저장 (List 등에)
2. 1에서 저장 한 좌표를 모두 큐에 푸쉬
   => 동시에 시작하는 것을 보장하도록 모델링 할 수 있다.
3. 이제 bfs 를 시작
4. 어떤 좌표에 방문 시점은 이전 좌표에 (방문 시점 + 1)
5. bfs 는 어떤 정점을 시작 위치에서 최단거리로 방문하는 특징이 있으므로, 잘못된(뒤늦은) 방문은없다.
6. 모든 토마토가 익을 시점이 필요하므로, bfs 로 방문 시점 중 최대 값을 구한다.
   => 모든 토마토가 익는 최소 일수가 된다. (bfs 특징을 고려)

 

 

[3. 코드]