N(1 ≤ N ≤ 1,000)개의 컴퓨터로 구성된 네트워크가 있다. 이들 중 몇 개의 컴퓨터들은 서로 네트워크 연결이 되어 있어 서로 다른 두 컴퓨터 간 통신이 가능하도록 되어 있다. 통신을 할 때에는 서로 직접 연결되어 있는 회선을 이용할 수도 있으며, 회선과 다른 컴퓨터를 거쳐서 통신을 할 수도 있다.
각 컴퓨터들과 회선은 그 성능이 차이가 날 수 있다. 따라서 각각의 직접 연결되어 있는 회선을 이용해서 통신을 하는데 걸리는 시간이 서로 다를 수 있다. 심지어는 직접 연결되어 있는 회선이 오히려 더 느려서, 다른 컴퓨터를 통해서 통신을 하는 것이 더 유리할 수도 있다. 직접 연결되어 있는 회선을 사용할 경우에는 그 회선을 이용해서 통신을 하는 데 드는 시간만큼이 들게 된다. 여러 개의 회선을 거치는 경우에는 각 회선을 이용해서 통신을 하는 데 드는 시간의 합만큼의 시간이 걸리게 된다.
어느 날, 해커가 네트워크에 침입하였다. 네트워크의 관리자는 우선 모든 회선과 컴퓨터를 차단한 후, 해커의 공격을 막을 수 있었다. 관리자는 컴퓨터에 보안 시스템을 설치하려 하였는데, 버전 문제로 보안 시스템을 한 대의 슈퍼컴퓨터에만 설치할 수 있었다. 한 컴퓨터가 공격을 받게 되면, 네트워크를 통해 슈퍼컴퓨터에 이 사실이 전달이 되고, 그러면 슈퍼컴퓨터에서는 네트워크를 이용해서 보안 패킷을 전송하는 방식을 사용하기로 하였다. 준비를 마친 뒤, 관리자는 다시 네트워크를 복구하기로 하였다. 이때, 다음의 조건들이 만족되어야 한다.
원래의 네트워크에 대한 정보가 주어졌을 때, 위의 조건을 만족하면서 네트워크를 복구하는 방법을 알아내는 프로그램을 작성하시오.
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.
첫째 줄에 복구할 회선의 개수 K를 출력한다. 다음 K개의 줄에는 복구한 회선을 나타내는 두 정수 A, B를 출력한다. 이는 A번 컴퓨터와 B번 컴퓨터를 연결하던 회선을 복구한다는 의미이다. 출력은 임의의 순서대로 하며, 답이 여러 개 존재하는 경우에는 아무 것이나 하나만 출력하면 된다.
4 5
1 2 1
1 4 4
1 3 2
4 2 2
4 3 3
3
1 2
3 1
4 2
이 문제는 처음에 최소 스패닝 트리 문제로 생각하고 크루스칼 알고리즘을 이용해서 풀려했으나 해당 문제의 요구와 조금 달라서 다익스트라 알고리즘을 이용해 풀 수 있었다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Main {
static ArrayList<Pair>[] map;
static int[] path;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
map = new ArrayList[N+1];
for(int i=1; i<=N; i++)
map[i] = new ArrayList<>();
path = new int[N+1];
for(int i=0; i<M; i++) {
input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
int cost = Integer.parseInt(input[2]);
map[start].add(new Pair(end, cost));
map[end].add(new Pair(start, cost));
}
solution(N);
System.out.println(N-1);
for(int i=2; i<=N; i++)
System.out.println(i+" "+path[i]);
}
public static void solution(int N) {
int[] dist = new int[N+1];
for(int i=1; i<=N; i++)
dist[i] = Integer.MAX_VALUE;
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.add(new Pair(1, 0));
dist[1] = 0;
while(!pq.isEmpty()) {
Pair temp = pq.poll();
for(Pair next : map[temp.end]) {
if(dist[next.end] > temp.cost+next.cost) {
dist[next.end] = temp.cost+next.cost;
path[next.end] = temp.end;
pq.add(new Pair(next.end, temp.cost+next.cost));
}
}
}
}
public static class Pair implements Comparable<Pair>{
int end;
int cost;
public Pair(int end, int cost) {
this.end = end;
this.cost = cost;
}
public int compareTo(Pair p) {
return this.cost > p.cost ? 1 : -1;
}
}
}