경로찾기

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

다시 푼 문제이다. DFS를 이해하고 있으면 쉬운 문제이다.

풀이

1. 각각의 정점에서 차례대로 DFS를 실행한다.
2. 연결된 정점이 있고 아직 방문하지 않았으면, 방문 체크 후에 연결된 정점에서 다시 DFS를 실행한다.
3. 경로를 출력한다.

예시

위의 경우를 생각해보자.

• 0을 시작으로 DFS를 실행한다.
  • 0과 연결된 정점은 1이다. 1은 아직 방문하지 않았으니 방문 체크를 한다.
  • 1을 시작으로 DFS를 실행한다.
  • 1과 연결된 정점은 2이다. 2는 아직 방문하지 않았으니 방문 체크를 한다.
  • 2를 시작으로 DFS를 실행한다.
  • 2와 연결된 정점은 0이다. 0은 아직 방문하지 않았으니 방문 체크를 한다.
  • 0과 연결된 정점은 1이다. 1은 이미 방문을 하였으니 방문하지 않는다.
  • DFS는 종료되고, 방문체크 된 곳이 0에서 이동 가능 한 정점이다.
• 1을 시작으로 DFS를 실행한다.
  • 이하 위와 같다.
• 2를 시작으로 DFS를 실행한다.
  • 이하 위와 같다.