백준 2211 네트워크 복구 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/2211

• 1번 컴퓨터가 슈퍼 컴퓨터

• 간선을 활용하여 모든 컴퓨터와 최단 경로로 연결해야함.

• 이때 최단 경로의 개수와 경로 자체를 (출발 정점, 끝정점) 형식으로 모두 출력하라.

2. 코드가 나오기까지 🛠️

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

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



public class Main {
    static class Edge{
        int start;
        int weight;
        int end;

        public Edge(int start, int end, int weight){
            this.start = start;
            this.end = end;
            this.weight = weight;
        }    }    static int V,E;
    static ArrayList<ArrayList<Edge>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        for(int i = 0; i <= V; i++){
            list.add(new ArrayList<>());
        }        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list.get(start).add(new Edge(start,end, weight));
            list.get(end).add(new Edge(end, start, weight));
        }        ArrayList<Edge> answer = dijkstra();
        System.out.println(answer.size());
        for(Edge row : answer){
            System.out.printf("%d %d\\n",row.start, row.end);
        }    }
    public static ArrayList<Edge> dijkstra(){
        ArrayList<Edge> answer = new ArrayList<>();
        int [] dashboard = new int [V+1];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        pq.add(new Edge(1,1,0));
        Arrays.fill(dashboard, Integer.MAX_VALUE);
        dashboard[1] = 0;
        while (!pq.isEmpty()){
            Edge now = pq.poll();
            if(now.weight > dashboard[now.end]) continue;
            if(!(now.start == 1 && now.end == 1)) answer.add(now);
            for(int i =0; i < list.get(now.end).size(); i++){
                Edge next = list.get(now.end).get(i);
                if(now.weight + next.weight >= dashboard[next.end]) continue;
                dashboard[next.end] = now.weight + next.weight;
                pq.add(new Edge(next.start, next.end, dashboard[next.end]));
            }        }        return answer;
    }
  }

4. 트러블 슈팅 or 배운 점📝