백준 | 14621번. 나만 안되는 연애 -최소비용 신장 트리

⬛ 백준 14621번. 나만 안되는 연애 - 최소비용 신장 트리

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

14621번: 나만 안되는 연애

문제

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
3. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.

만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

문제 이미지

이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.

입력

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

출력

깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

---

💚나의 풀이

• 주의할 점은 1) ‘모든 학교를 연결할 경로 없을 경우 -1을 출력해야 한다’는 것과 2) 여초 학교는 남초 학교와 연결이 되어야 한다는 것이다.

1) 모든 학교를 연결할 경로가 없을 경우를 처리

• 처음에 계속 NullPointer 이 떠서 왜 그런지 보았는데 PQ상에서 다음 사용할 조건 만족하는 간선을 뽑을 떄 더 이상 없을 경우 null이 떴다. 그리고 이 경우는 ‘모든 학교를 연결할 경로가 없을 경우’가 되므로 flag를 걸어주고 break로 탈출하여 출력을 처리해야 한다.
• [참고] 이전에 비슷하게 최소스패닝트리 문제를 풀 때 NullPointer 가 떠서 비슷하게 해결한 적이 있다. 앞으로도 비슷한 조건을 보면 주의하자. 

2) 해여초 학교와 남초 학교가 연결될 도로 잇는 방식

• String[] 배열에 각 i번째 학교의 W, M 정보를 담아둔다.
• 최소 스패닝 트리는 Edge 리스트를 사용하여 가중치 낮은 간선을 우선으로 연결한다는 점과 총 간선의 개수는 N-1개라는 점, 사이클을 형성하면 안된다는 점을 주의하면서 작은 가중치 간선들을 차례로 이어붙인다.
• 이어붙일 때 사이클 형성하지 않으면서 team정보가 다른 정점들을 이어붙인다.

package to_0911_8;

import java.util.PriorityQueue;
import java.util.Scanner;

/*14621번. 나만 안되는 연애 - 최소 스패닝 트리 문풀 */
class Edge implements Comparable<Edge>{ 
	int s;
	int e;//끝점
	int val;//가중치
	Edge(int s, int e, int val){
		this.s= s;
		this.e= e;
		this.val= val;
	}
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.val - o.val;//가중치 낮은 거 우선 순위 
	}
}
public class Main {
	static int N, M;//정점과 간선 개수 
	static int[] parent;
	//find
	static int find(int a) {
		if(a==parent[a]) return a;
		else return parent[a] = find(parent[a]);
	}
	//union
	static void union(int a, int b) {
		a= find(a);
		b =find(b);
		if(a!=b) {
			parent[b] = a;
		}
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		
		String[] team = new String[N+1];
		for(int i=1; i<=N; i++) {
			team[i] = kb.next();
		}
		
		parent = new int[N+1];
		for(int i=1; i<=N; i++) parent[i]=i;
		
		//가중치 적은 거 운선 정렬
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		
		for(int i=0; i<M; i++) {
			int a =kb.nextInt();//얘로 자기 팀 확인하고 
			int b= kb.nextInt();
			int x = kb.nextInt();
			pQ.offer(new Edge(a, b, x));//담고 
		}
		
		int useEdge = 0;
		int useCost = 0;
		boolean flag = true;//이거로 연결 상태 
		
		while(useEdge <N-1){
			//가장 낮은 가중치를 뽑고 
			Edge cur = pQ.poll();
			if(cur == null && useEdge < N-1) { 
				flag = false;//연결 끊김 다음 연결할 정점이 X
				break;
			}
			//둘이 서로 사이클 형성 X && 두 정점의 학교 W , M이 다른 경우에 한해서 union
			if(find(cur.s) != find(cur.e)) {
				//팀도 다른 팀일 경우에만 
				if(!team[cur.s].equals(team[cur.e])){
					union(cur.s, cur.e);
					useCost += cur.val;//가중치 합치고 
					useEdge++;
				}
			}
		}
		
		if(!flag) {
			//연결 끊긴 상태라면 
			System.out.println("-1");
		}else System.out.println(useCost);
	}
}