[백준] 1697 - 숨바꼭질 [Python(파이썬)]

문제

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

1697번: 숨바꼭질

 

풀이

언뜻 문제만 DFS를 이용해 백트래킹을 해야 하는 문제로 보인다. 하지만 이 문제는 최단 경로를 구하는 일차원 그래프 탐색 문제였다. 오히려 다른 BFS문제들보다 더 심플하다. 방문처리만 조금 신경써준다면 수월하게 해결할 수 있다. 미리 그래프의 크기만큼의 리스트를 선언하거나 집합을 이용해서 O(1) 안에 방문처리를 해줄 수 있도록 하자.

 

코드