MST자바구현

BOJ - 나만 안되는 연애 14621번 (JAVA)

❓ 문제 - 백준 나만 안되는 연애 14621번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/14621) 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 📝 문제해결법 1. 이 문제는 MST(최소신장트리)로 풀이했다. 부모 찾기와 합집합을 구현하여 사이클이 생기지 않는 조건에서 최소신장트리를 구현하면서 최소비용을 구한다. 그러나 문제에서 주어진, 사심 경로에 서로 연결될 때 서로 다른 성별만 연결될 수 있으므로 애초에 간선에 대한 ..