[백준 2211] 네트워크 복구 - JAVA

문제 링크

문제 정의

• $N$개의 컴퓨터
• $M$개의 회선 존재
• $1$번 컴퓨터를 슈퍼 컴퓨터로 설정했을 때
  • 슈퍼컴퓨터(1번)에서 다른 모든 컴퓨터로 가는 최단 경로를 유지하면서
  • 연결에 필요한 전체 간선(회선)의 수를 최소화하여 트리 구조를 복구

접근 방법

주요 포인트는 세 가지입니다.

1. 최단 거리 보존

슈퍼컴퓨터와 각 컴퓨터가 통신할 때
복구 전의 최단 거리보다 멀어지면 안 됩니다.

이 조건 때문에 반드시 다익스트라 알고리즘을 사용해야 합니다.

2. 간선 개수 최소화

모든 정점을 연결하면서
간선 수를 최소화하는 모델은 트리(Tree)입니다.

정점이 $N$개일 때 간선은 $N-1$개가 됩니다.

3. 중복 제거

여러 경로를 복구하다 보면 겹치는 구간이 생길 수 있습니다.
하지만 parent[] 배열을 이용해
각 정점의 직전 노드 하나만 선택하면
자연스럽게 중복 없는 최소 간선 집합을 구할 수 있습니다.

코드

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

class Edge {
	int v;
	int w;
	Edge edge;

	public Edge (int v, int w, Edge edge) {
		this.v = v;
		this.w = w;
		this.edge = edge;
	}
}

public class Main {
	static StringTokenizer st;
	static Edge[] graph;
	static int N, M;

	public static void main(String[] args) throws Exception {
		init();
		dijkstra();
	}

	static void init() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		graph = new Edge[N+1];
		while (M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			graph[u] = new Edge(v, w, graph[u]);
			graph[v] = new Edge(u, w, graph[v]);
		}
	}

	static void dijkstra() {
		PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
		pq.offer(new int[]{1, 0});

		int[] dist = new int[N+1];
		int[] parent = new int[N+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1] = 0;

		while (!pq.isEmpty()) {
			int[] edge = pq.poll();
			int v = edge[0];
			int w = edge[1];

			if (dist[v] < w) continue;

			for (Edge next = graph[v]; next != null; next = next.edge) {
				int nv = next.v;
				int nw = dist[v] + next.w;

				if (dist[nv] > nw) {
					dist[nv] = nw;
					parent[nv] = v;
					pq.offer(new int[]{nv, nw});
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(N-1).append("\n");
		for (int i = 2; i <= N; i++) {
			if (parent[i] != 0) {
				sb.append(i).append(" ").append(parent[i]).append("\n");
			}
		}

		System.out.print(sb);
	}
}