백준 1697, 12851 - 숨바꼭질 1, 2 (Python)

1697번은 dp로 풀고 dp로 푸는 게 맞는 줄 알았다.

12851이 안 풀려서 보니 bfs였던 문제.

​

1697 - dp 풀이

​

단순하게 dp를 이용해 계속 i-1, i+1, i//2를 비교해가며 작은 것으로 업데이트 하는 방법이다.

정확한 경로를 알아야 할 필요가 없고 시간만 필요하다면 이런 풀이도 가능은 하다.

그러나 사실상 정방향으로 계속 가면 그만이기 때문에 굳이 dp를 쓰는 메리트는 없는 문제.

​

1697-bfs 풀이

이런 식으로 시작점부터 쭉 끝까지 가면서 특정 지점까지 가는 지점을 업데이트 해주면 끝이다.

​

12851

12851은 동일하게 순회를 돌되, visited를 이중배열로 만들고 두 번째 항목에는 방문 횟수를 기록한다.