Union-Find. [1976]

[1. 문제 설명]

N 개의 도시가 있고, 각 도시 사이는 연결될 수도 안될 수도 있다.

여행 일정이 주어졌을 때, (방문할 도시들의 순서) 이 여행 경로가 가능한지 확인한다.

여행 일정을 만족하기 위해, 다른 도시를 경유해서 갈 수도 있다.

 

ex) 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

 

 

 

[2. 풀이 접근]

이 문제에서 bfs 등으로 여행 경로를 확인하기에는 무리가 있다.

왔던 길을 되돌아가도 되기 때문이다.

 

그래서 일반적인 그래프 순회로 풀이하기에는 까다로울 수 있다.

 

여기서는 상호 배타적 집합을 통해 풀 수 있다.

 

여행 계획에 있는 도시들이 모두 같은 집합에 있다면,

여행 계획을 만족하는 경로가 반드시 존재하기 때문이다.

(왔던 길을 되돌아가는 한이 있더라도)

 

 

 

[3. 코드]