Algorithm/ACM-ICPC

[ID: 2211] 네트워크 복구

마산와사비 2020. 2. 1. 15:27
 

2211번: 네트워크 복구

첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다.

www.acmicpc.net

  • 풀이
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static int INF = Integer.MAX_VALUE;
	public static int[] dist;
	public static Map<Integer, Edge> edges;

	static class Graph {
    		Map<Integer, ArrayList<Node>> graph = new HashMap<>();
    	
        	public void addNode(int node, Node adjNode) {
    			ArrayList<Node> adjNodes = graph.get(node);
    			
    			if(adjNodes == null) {
    				adjNodes = new ArrayList<>();
    			}
    			
    			adjNodes.add(adjNode);
    			graph.put(node, adjNodes);
    		}
    		
    		public ArrayList<Node> getAdjNodes(int node) {
    			return graph.get(node);
    		}
    	}
    
	static class Node implements Comparable<Node> {
		int nextNode;
		int weight;
		
		public Node(int nextNode, int weight) {
			this.nextNode = nextNode;
			this.weight = weight;
		}
		
		public int getNode() {
			return this.nextNode;
		}
		
		public int getWeight() {
			return this.weight;
		}

		@Override
		public int compareTo(Node o) {
			return this.weight < o.weight ? -1 : 1;
		}
	}
	
	static class Edge {
		int start;
		int end;

		public Edge (int start, int end) {
			this.start = start;
			this.end = end;
		}
		
		public int getStart() {
			return this.start;
		}
		
		public int getEnd() {
			return this.end;
		}
	}
	
	public static void getMinDistance(int start, int end, Graph graph) {
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.add(new Node(start, 0));

		while(!queue.isEmpty()) {
			Node curNode = queue.remove();
			ArrayList<Node> adjNodes = graph.getAdjNodes(curNode.getNode());
			
			for(Node nextNode : adjNodes) {
				if(dist[curNode.getNode()] < curNode.weight) {
					continue;
				}
				
				if(dist[curNode.getNode()] + nextNode.getWeight() < dist[nextNode.getNode()]) {
					dist[nextNode.getNode()] = dist[curNode.getNode()] + nextNode.getWeight();
					queue.add(nextNode);
					edges.put(nextNode.getNode(), new Edge(curNode.getNode(), nextNode.getNode()));
				}
			}
			
		}
		
		System.out.println(edges.size());
		for (int i = 2; i <= end; i++) {
			System.out.println(edges.get(i).getStart() + " "+ edges.get(i).getEnd());
		}
	}
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		dist = new int[N+1];
		Arrays.fill(dist, INF);
		dist[1] = 0;
		Graph graph = new Graph();
		edges = new HashMap<Integer, Edge>();
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			graph.addNode(start, new Node(end, weight));
			graph.addNode(end, new Node(start, weight));
		}
		
		getMinDistance(1, N, graph);

	}
}

 

  •  NOTE
    • Dijkstra 기본 문제 
    • 단, 각 정점까지 가는 최단경로 간선을 같이 출력해야 한다.
      • Map을 이용하여 각 정점을 키 값으로 마지막으로 연결된 정점을 저장하는 형태로 풀이