[JAVA] 백준 1922 : 네트워크 연결

문제

1922번: 네트워크 연결

 

풀이방법

한 정점에서 모든 정점을 연결하는데에 드는 비용을 최소로 하는 문제이다.

크루스칼과 프림을 사용할 수 있는데, 프림을 안써본지 오래되어서 프림으로 코드를 구성해보았다.

 

인접리스트로 양방향 연결을 먼저 해준다음 임의의 시작점에서 출발시키면된다.

프림은 방문배열과 각 정점의 최소비용을 저장할 정점 크기만큼의 1차원 배열을 사용한다.

최소비용을 저장할 배열은 최대값으로 초기화해준다.

 

필자는 우선순위큐를 활용한 프림을 구성하였는데, 그렇기 때문에 비용에 따라 오름차순 정렬을 통해 비용이 적은 것 부터 탐색하도록하였다.

임의의 시작 정점을 정하였으면 해당 부분을 큐에 넣어주고, 최소정점배열의 임의의 정점을 0으로 초기화해준다.

 

그 이후 큐가 비거나 모든 정점을 방문했을 경우에 반복문이 종료된다.

반복문 안에서는 해당 정점을 방문 체크를 해주고 결과값에 비용을 더해준다.

그 다음 해당 정점에서 갈 수 있는 다른 모든 정점 중 현재 저장된 비용보다 더 적게 갈 수 있는 모든 간선을 큐에 넣어주고 반복한다.

 

 

코드

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[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		ArrayList<Network>[] comList = new ArrayList[N + 1];
		int[] minEdge = new int[N + 1];
		boolean[] visit = new boolean[N + 1];
		
		for (int i = 1; i <= N; i++) {
			comList[i] = new ArrayList<>();
			minEdge[i] = Integer.MAX_VALUE;
		}
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			comList[a].add(new Network(b, c));
			comList[b].add(new Network(a, c));
		}
		
		int result = 0, nodeCnt = 0;
		
		PriorityQueue<Network> q = new PriorityQueue<>();
		q.offer(new Network(1, 0));
		minEdge[1] = 0;
		
		while (!q.isEmpty()) {
			Network network = q.poll();
			if (visit[network.end]) continue;
			
			visit[network.end] = true;
			result += network.cost;
			
			if (++nodeCnt == N) break;
			
			for (int i = 0; i < comList[network.end].size(); i++) {
				int next = comList[network.end].get(i).end;
				int cost = comList[network.end].get(i).cost;
				
				if (!visit[next] && minEdge[next] > cost) {
					minEdge[next] = cost;
					q.offer(new Network(next, cost));
				}
			}
			
		}
		System.out.println(result);
	}
	
	static class Network implements Comparable<Network> {
		int end;
		int cost;
		
		Network (int end, int cost) {
			this.end = end;
			this.cost = cost;
		}

		@Override
		public int compareTo(Network o) {
			// TODO Auto-generated method stub
			return cost - o.cost;
		}
	}
}