2211번: 네트워크 복구

• N개의 정점(V)과 M개의 간선(E), 그리고 간선의 비용이 주어진다.
• 모든 정점을 방문할 수 있어야한다.
• 정점으로의 경로는 최소 개수의 간선을 사용하면서, 간선의 비용이 최소이어야한다.
• 이때, 필요한 간선의 개수와 사용된 간선들을 출력하라.

접근

간선 비용이 최소

• 전형적인 다익스트라 알고리즘의 조건이다.
  

간선의 개수가 최소 + 모든 정점을 방문할 수 있어야한다

• 문제 조건을 통해, 시작점으로부터 모든 정점을 방문할 수 있다.
• 따라서 한 정점으로부터 시작하는 다익스트라 알고리즘의 경로를 트리로 만들 경우, N개의 정점을 지나며 사이클이 존재하지 않으므로 언제나 N-1개의 간선을 가지게 된다.

사용된 간선을 출력

• 다익스트라 알고리즘을 사용해 이동한 경로를 출력해야한다.
• 사이클이 존재하지 않는 트리이므로, 모든 정점이 하나의 진입점(Origin)을 가진다.
• 따라서, 어느 정점으로부터 왔는지 저장하기만 하면 된다.

코드

import java.io.*;
import java.util.*;

public class Main {

	static StringBuilder str;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		init(in);
		
		solve(in);			
	}
	
	static int nComputer;
	static int nLines;
	static ArrayList<Line>[] line; 
	public static void init(BufferedReader in) throws IOException{
		StringTokenizer tokens = new StringTokenizer(in.readLine());
		nComputer = Integer.parseInt(tokens.nextToken());
		nLines = Integer.parseInt(tokens.nextToken());
		
		line = new ArrayList[nComputer+1];
		for(int i = 0; i < nComputer+1; i++) {
			line[i] = new ArrayList<>();
		}
		
		for(int i = 0; i < nLines; i++) {
			tokens = new StringTokenizer(in.readLine());
			int from = Integer.parseInt(tokens.nextToken());
			int to = Integer.parseInt(tokens.nextToken());
			int time = Integer.parseInt(tokens.nextToken());
			
			line[from].add(new Line(to, time));
			line[to].add(new Line(from, time));
		}
	}
	
	public static void solve(BufferedReader in) throws IOException {
		originalNetwork();
		System.out.println(repairedLine());
	}
	
	static int[] originalTime;
	static int[] origin;
	static void originalNetwork() {
		
		originalTime = new int[nComputer+1];
		origin = new int[nComputer+1];
		Arrays.fill(originalTime, Integer.MAX_VALUE);
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		pq.add(1);
		originalTime[1] = 0;
		origin[1] = 0;
		
		while(!pq.isEmpty()) {
			int cur = pq.poll();
			int time = originalTime[cur];
			
			for(Line next : line[cur]) {
				if(originalTime[next.dest] <= time + next.time) continue;
				
				pq.add(next.dest);
				originalTime[next.dest] = time + next.time;
				origin[next.dest] = cur;
			}
		}
		
//		for(int t : origin) {
//			System.out.println(t);
//		}
	}
	
	static String repairedLine() {
		StringBuilder str = new StringBuilder();
		
		str.append(nComputer-1).append("\n");
		
		ArrayDeque<Integer> q = new ArrayDeque<>();
		
		q.add(1);
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			
			for(Line next : line[cur]) {
				if(origin[next.dest] != cur) continue;
				
				q.add(next.dest);
				str.append(cur).append(" ").append(next.dest).append("\n");
			}
		}
		
		return str.toString();
	}
	
	static class Line{
		int dest;
		int time;
		public Line(int d, int t) {
			dest = d;
			time = t;
		}
	}
}

회고

최소 간선을 사용해야한다는 조건때문에 뭔가 놓치는 부분이 있는지, 다익스트라로 했을 때 반례가 존재하는지, 꽤 많은 시간 고민을 했다.
그러나 결국 문제의 최소 간선 개수를 사용해야한다는 조건은 다익스트라 알고리즘을 사용하여 트리를 구성하게 되면 자동충족이 되었고, 사이클이 존재하지 않는 트리이기 때문에 사용된 간선 개수는 N-1개로 고정이 된다.
풀이 자체는 단순하지만, 문제의 조건으로 인해 생각을 많이 하게 함정을 파는 문제라고 느꼈다.