최소신장트리. [14621]

[1. 문제 설명]

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

---

[2. 풀이 접근]

그래프 문제 관련 함정

• 같은 edge 인데, weight 가 다른 edge 가 여러 개가 입력으로 있을 수 있다.
• 크루스칼 알고리즘 같은 경우는 우선순위 큐를 사용해서, 최소 weight 가 아닌 edge 는 결과적으로 버려진다.
• 그러나 최소 신장 트리 문제가 아닌 경우에는, 반드시 최소 weight 인 edge 를 사용하도록 데이터 변경이 필요하다.

이번 문제에서 나름 함정(?)

• edge 를 구성하는 두 노드의 성향이 같은 경우, 이 edge 는 사용해서는 안된다.
  => 문제 조건이었다.

---

[3. 코드]