백준 12851. 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

시작점 N에서 K까지 최단거리를 구해야 한다.

여기까지라면 그냥 기본 bfs 돌리면 되는데, 최단거리로 가는 방법의 수까지 구해야 한다.

 

이말은 즉 한번 방문한 지점도 다시 방문할수도 있다는 뜻이므로 int형 배열을 만들어 해당 지점 도달하는데 걸리는 최단거리 값을 저장하고, 다음 지점으로 이동할때 걸리는 시간이 이미 기록된 시간 보다 크다면 이동하지 않도록 한다.

 

목적지점에 최초로 도착했을때 걸린 시간이 최단거리이다.

따라서 두번째 도착했을때 부터는 방법의 수값을 증가시키면 된다. 

그리고 당연히 목적지점 도착했을 때는 continue 문으로 더 이상 이동은 막아야 한다.