백준 2211 (네트워크 복구) - java

https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

출력(간선) 처리를 제외하고는 평범한 다익스트라 문제이다.

past[] 배열을 사용하여 해당 정점에 도착하기 위해 바로 전에 건너야 할 정점을 알 수 있었다.

위 문제에서 구해야 하는 것은 간선이기 때문에 다음과 같은 방식으로 출력을 해결했다.

 

지금 생각해보니 굳이 set을 사용하지 않아도 되는 것이었다. 2번째 정점부터 n번째 정점까지 (해당 정점 바로 직전 정점) 을 저장하면 그것이 간선이다.

        HashSet<String> set = new HashSet<>();

        for(int i=2;i<=n;i++)
        {
            int small = Math.min(i,past[i]);
            int big = Math.max(i,past[i]);

            set.add(small+" "+big+"\n");
        }

        System.out.println(set.size());
        for(String go : set)
        {
            System.out.print(go);
        }

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        ArrayList<Edge>[] graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++)
        {
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());


            graph[x].add(new Edge(y,c));
            graph[y].add(new Edge(x,c));
        }

        search(graph);
        br.close();
    }

    static void search(ArrayList<Edge>[] graph)
    {
        boolean[] visit = new boolean[n+1];
        int[] dis = new int[n+1];
        int[] past = new int[n+1];

        for(int i=1;i<=n;i++)
        {
            dis[i] = Integer.MAX_VALUE;
        }
        dis[1] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x,y) -> x.c - y.c
        );

        pq.add(new Edge(1,0));

        while(!pq.isEmpty())
        {
            Edge cur = pq.poll();

            if(visit[cur.v])
                continue;

            visit[cur.v] = true;

            for(Edge next : graph[cur.v])
            {
                if(dis[cur.v] + next.c < dis[next.v])
                {
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Edge(next.v , dis[next.v]));
                    past[next.v] = cur.v;
                }
            }
        }

        HashSet<String> set = new HashSet<>();

        for(int i=2;i<=n;i++)
        {
            int small = Math.min(i,past[i]);
            int big = Math.max(i,past[i]);

            set.add(small+" "+big+"\n");
        }

        System.out.println(set.size());
        for(String go : set)
        {
            System.out.print(go);
        }
    }
}

class Edge
{
    int v;
    int c;

    Edge(int v,int c)
    {
        this.v = v;
        this.c = c;
    }
}