14621 나만 안되는 연애_Prim

14621번: 나만 안되는 연애 (acmicpc.net)

14621번: 나만 안되는 연애

 

Univ 클래스를 Comparator를 implements 하면 Priority Queue에 넣을 때 cannot be cast to java.lang.Comparable 라는 에러가 뜬다.

Comparable : 이 인터페이스를 구현한 객체 스스로에게 부여하는 한 가지 기본 정렬 규칙을 설정하는 목적으로 사용한다.

Comparator : 이 인터페이스를 구현한 클래스는 정렬 규칙 그 자체를 의미하며, 기본 정렬 규칙과 다르게 원하는대로 정렬순서를 지정하고 싶을 때 사용한다.

 

package Prim;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Baekjoon_14621_나만안되는연애 {
	
	public static class Univ implements Comparable<Univ> {

		int node, weight;
		char sex;
		
		public Univ(int node, int weight, char sex) {
			this.node = node;
			this.weight = weight;
			this.sex = sex;
		}

		@Override
		public int compareTo(Univ o) {
			return this.weight - o.weight;
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		char[] university = new char[N+1];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			university[i] = st.nextToken().charAt(0);
		}
		
		boolean[] visited = new boolean[N+1];
		ArrayList<Univ> list[] = new ArrayList[N+1];
		
		for(int i = 0; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int target = Integer.parseInt(st.nextToken());
			int dis = Integer.parseInt(st.nextToken());
			list[start].add(new Univ(target, dis, university[target]));
			list[target].add(new Univ(start, dis, university[start]));
		}
		
//		for(int i = 0; i < N+1; i++) {
//			System.out.println();
//			for(int j = 0; j < list[i].size(); j++) {
//				System.out.print(list[i].get(j).node + " " + list[i].get(j).sex);
//				System.out.print(" ");
//			}
//		}
		
		// 현재 연결된 정점들 중에 가장 가중치 적은 간선 고를 수 있음
		PriorityQueue<Univ> q = new PriorityQueue<>(); 
		// 1번 노드 넣어주자
		q.add(new Univ(1,0,university[1]));
		
		int ans = 0;
		while(!q.isEmpty()) {
			
			Univ univ = q.poll();
			//System.out.println(univ.node);
			
			// 방문했으면 패스
			if(visited[univ.node]) continue;
			visited[univ.node] = true;
			
			ans += univ.weight; // 가중치 증가
			
			// 방문하지 않은 노드 큐에 넣어줌
			for(Univ next : list[univ.node]) {
				
				if(!visited[next.node] && next.sex != univ.sex) {
					//System.out.println(next.sex + " " +univ.sex);
					q.offer(next);
				}
			}
			
		}
		for(int i = 1; i < N+1; i++) {
			if(visited[i] == true) continue;
			System.out.println(-1);
			return;
		}
		System.out.println(ans);
		
	}

}