[BOJ]13549번: 숨바꼭질 3

 

문제: https://www.acmicpc.net/problem/13549

---

다익스트라로 해결하였습니다.

특정 좌표 X에서 수빈이가 움직일 수 있는 위치는 세 가지 입니다.

 

1. X-1

2. X+1

3. 2X

 

다익스트라로 해결한 이유는 두 배씩 뛰는 좌표의 경우 시간의 영향을 받지 않습니다.

그러므로 그냥 단순히 방문했다고 visited[] 배열을 true / false로만 표시한다면

더 빠른 시간에 특정 좌표 X에 도착해도 이미 visited[] 이 true라면 다시 탐색할 수 없습니다.

그러므로 큐에서 늦게 나온 값이라도 이미 저장되어있는 visited[] 시간보다 빠르면 갱신해줍니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13549.cc