ALGORITHM/BOJ
[BOJ] 14621번 나만 안되는 연애 (C++)
yegyeom
2022. 3. 3. 14:38
문제 (https://www.acmicpc.net/problem/14621)
14621번: 나만 안되는 연애
입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의
www.acmicpc.net
최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다.
특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다.
남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다.
만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(BD) + 5(BE) + 10(AC) = 23이 될 것이다. 하지만 조건에 의해 오른쪽 사진과 같은 결과가 나온다.
만약 모든 학교를 연결하는 경로가 없을 경우 -1을 출력해야 한다. 두 노드가 union이 될 때마다 카운팅을 하여 카운트 수가 n - 1보다 작다면 -1을 출력하도록 했다.
[소스코드]
