[14621] 나만 안되는 연애 - Java[자바]

 

 

| 문제 링크

 

 

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

14621번: 나만 안되는 연애

 

 

 

 

---

 

 

 

 

| 문제

 

1. N개의 정점과 M개의 간선이 주어집니다.
   (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)
2. N개의 정점은 W 혹은 M으로 성질이 구분됩니다.
3. 학교간 연결된 간선 중 성질이 다른 간선을 이용해 모든 학교가 연결되는 최소한의 길이를 출력하시오.
   모든 학교가 이어질 수 없다면 -1을 출력하시오.

 

 

 

---

 

 

 

 

| 풀이

 

1. 최소 스패닝 트리 문제이며, 학교의 성질이 다른 경우에만 이어질 수 있다는 조건을 추가해줍니다.
2. 우선 학교 별 성별을 나타내는 String[] 배열을 생성해 학교 별 성별을 입력해 줍니다.
3. 학교 별 연결된 간선의 정보를 인접리스트로 입력해줍니다.
   인접리스트는 Node클래스(to, w)를 사용.
4. 프림 알고리즘(크루스칼 알고리즘도 동일)을 통해 임의의 학교를 가중치가 0인 시작점으로 정합니다.
   우선순위 큐를 통해 가중치가 적은 정점들을 가장 앞으로 정렬
5. 해당 학교로부터 이어져있는 학교들을 조회하며, 이미 방문하였거나, 성별이 같은 학교는 continue합니다.
   5-1) 학교 간의 길이를 누적합니다.
   5-2) 연결된 학교의 개수를 누적합니다.
6. 반복문이 끝나고 연결된 학교의 개수가 전체 학교의 개수와 상이한 경우 -1을 출력, 동일한 경우 누적된 학교 간의 길이를 출력합니다.

 

 

 

---

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Node14621 implements Comparable<Node14621>{
	int to;
	int w;
	
	public Node14621(int to, int w) {
		this.to=to;
		this.w=w;		
	}
	
	@Override
	public int compareTo(Node14621 o1) {
		return this.w-o1.w;
	}
	
}

public class Main {
	
	public static int N;
	public static int sum = 0;
	public static int cnt = 0;
	public static String[] gender;
	public static boolean[] flag;
	public static List<Node14621>[] graph;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		gender = new String[N+1];
		flag = new boolean[N+1];
		graph = new ArrayList[N+1];
		for(int i = 1; i<=N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		//학교별 성별 입력
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<=N; i++) {
			gender[i] = st.nextToken();
		}
		
		//인접리스트 생성, 양방향 연결
		for(int i = 1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			graph[a].add(new Node14621(b,w));
			graph[b].add(new Node14621(a,w));
		}
		
		prim();
		
		//모든 학교가 연결되지 못했다면 -1 출력
		if(cnt != N)
			bw.write("-1");
		else
			bw.write(String.valueOf(sum));
		br.close();
		bw.close();
	}
	
	public static void prim() {
		Queue<Node14621> que = new PriorityQueue<>();
		//임의의 시작점을 가중치를 0으로 설정해 줍니다.
		que.add(new Node14621(1,0));
		
		while(!que.isEmpty()) {
			Node14621 now = que.poll();
			//이미 방문한 노드라면 continue
			if(flag[now.to])
				continue;
			//방문처리 해주며, 가중치를 더해 길이를 누적해갑니다.
			flag[now.to] = true;
			sum+=now.w;
			//cnt는 거쳐가는 학교의 개수이며, 반복문이 끝나고 cnt가 N과 다른 경우에는 -1을 출력
			cnt++;
			for(Node14621 next : graph[now.to]) {
				//이미 방문한 노드거나 이동알하는 학교의 성별이 같은 경우 continue
				if(flag[next.to] || gender[next.to].equals(gender[now.to]))
					continue;
				que.add(next);
			}
		}
	}

}