사실 이 문제를 보고 가장 먼저 든 생각은 최소 스패닝 트리의 해법과 비슷하게 풀면 된다는 것이다. 특히 Kruskal 알고리즘 해법과 되게 비슷한 느낌이 들었다. 정확하게 이 문제는 스패닝 트리를 구하는 것이 아니다. 왜냐하면, 출발과 목적 지점을 포함하기만 하면 되지 모든 노드들을 전부 방문할 필요는 없기 때문이다. 하지만 Kruskal 알고리즘 기법을 활용하겠다고 마음을 먹은 이유는 다음과 같다. 1. 결과적으로 길이 최대가 되게끔 계속해서 만들어야 한다. 2. 즉 이러한 알고리즘은 사실상 최소 값들을 priority_queue에 저장하고 탐욕적으로 집합을 만드는 Kruskal 알고리즘과 매우 유사하다. 3. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 ..