MST문제추천

BOJ - 정복자 14950번 (JAVA)

❓ 문제 - 백준 정복자14950번 - JAVA 풀이법 출처 (https://www.acmicpc.net/problem/14950) 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 📝 문제해결법 1. 이 문제는 MST(최소신장트리)로 풀이했다. 부모 찾기와 합집합을 구현하여 사이클이 생기지 않은 조건에서 최소신장트리를 만들어 모든 노드를 최소 비용으로 연결하도록 구현한다. 그러나 문제에서 최소신장트리를 구현하면서 최소 비용을 구할 때, 노드가 연결될 때마다 비용 t가 계속 추가적으로 증가한다는 것이다. 이것을 노드..

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(최소신장트리)로 풀이했다. 부모 찾기와 합집합을 구현하여 사이클이 생기지 않는 조건에서 최소신장트리를 구현하면서 최소비용을 구한다. 그러나 문제에서 주어진, 사심 경로에 서로 연결될 때 서로 다른 성별만 연결될 수 있으므로 애초에 간선에 대한 ..