[BOJ]1976번: 여행 가자

 

www.acmicpc.net/problem/1976

---

여러 가지 방법으로 풀 수가 있겠습니다.

 

제가 해결한 방법은 Floyd + BFS 입니다.

 

1. 플로이드를 통해 모든 가능한 정점쌍을 연결해줍니다.

2. 주어진 플로이드를 가지고 N개의 노드에 대해 BFS를 돌아서 컴포넌트를 나눠줍니다.

3. 여행 경로에 속한 노드가 모두 한 컴포넌트에 속해있다면 순서가 어떻든 모두 방문이 가능합니다.

---

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