백준 1922 - 네트워크 연결(Java)

www.acmicpc.net/problem/1922

1922번: 네트워크 연결

1. 유형

그래프, 구현, MST

 

2. 자료구조

우선순위큐, 어레이리스트

 

3. 기능

- 인접리스트를 만들어서 가중치 그래프 만들기

- 프림알고리즘

 

4. 풀이

프림알고리즘만 알고 있었다면 쉽게 풀 수 있는 문제.

 

minRute[N+1]-> N까지 연결된 가장 짧은 가중치를 넣는다.

minRute보다 더 짧다면 갱신 시켜준다.

끝.

 

코드.

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

public class Main {
	static int N, M,total;
	static ArrayList<Pair> list[];
	static class Pair implements Comparable<Pair>{
		int node, w;
		public Pair(int node, int w) {
			// TODO Auto-generated constructor stub
			this.node = node;
			this.w=w;
		}
		@Override
		public int compareTo(Pair o) {
			return this.w - o.w;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(in.readLine());
		M = Integer.valueOf(st.nextToken());
		list = new ArrayList[N+1];
		for(int i=0; i<N+1; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(in.readLine());
			int u = Integer.valueOf(st.nextToken());
			int v = Integer.valueOf(st.nextToken());
			int w = Integer.valueOf(st.nextToken());
			list[u].add(new Pair(v,w));
			list[v].add(new Pair(u,w));
		}
		prim();
		System.out.println(total);
	}
	
	static void prim() {
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		total=0;
		int minRute[] = new int[N+1];
		for(int i=2; i<N+1; i++) {
			minRute[i] = Integer.MAX_VALUE;
		}
		boolean visit[] = new boolean[N+1];
		pq.add(new Pair(1, 0));
		while(!pq.isEmpty()) {
			Pair cur = pq.poll();
			if(visit[cur.node]) {
				continue;
			}
			visit[cur.node] = true;
			total+=cur.w;
			for(Pair next : list[cur.node]) {
				if(!visit[next.node] && minRute[next.node] > next.w) {
					minRute[next.node] = next.w;
					pq.add(next);
				}
			}
		}
	}
}

5. 느낀점

MST알고리즘을 복습하기에 좋은 문제.