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

문제 링크

---

풀이

문제를 읽고 mst를 구현하면 되는 문제라고 생각하여 mst로 문제를 풀이해 보았으나 실패하였다. 1번 컴퓨터가 보안 시스템을 설치할 슈퍼 컴퓨터라고 명시되어있기 때문에, 모든 정점에 대해 1번과의 거리가 최소가 되도록 하는 간선들을 중복되지 않도록 찾아야 한다.

1과의 거리가 최소가 되도록 다익스트라 알고리즘을 사용하였고, 그 최소 거리를 출력하는것이 아니라 간선들을 찾아 출력해야 하므로 다익스트라 진행 과정 중 최소 거리 갱신과 동시에 간선들의 정보를 저장한다.

1. 1부터 index까지 최단거리 중 속하는 간선들을 저장할 Vector 배열을 생성한다.
2. 1번 정점을 기준으로 잡고 Priority Queue에 삽입한 후 다익스트라 알고리즘을 진행한다.
3. 현재 노드를 cur, 다음 갱신할 목표 노드를 next 라고 했을 때 Vector[next]를 clear시키고 Vector[cur]에 있는 간선 정보들 + cur와 next를 이어 주는 간선 정보를 저장한다.
   최소 거리가 갱신될 때 마다 이 과정을 진행해주면 1번 정점과의 최소 거리를 유지함과 동시에 유지하기 위한 간선들의 정보가 갱신된다.
4. 다익스트라 알고리즘 진행이 완료되면 Vector 배열에 저장한 모든 간선 정보들을 중복을 제거하고 출력한다. 이 과정에서 필자는 visit 2차원 배열을 만들어 해결하였다.

주의할 점

• 앞서 서술하였듯이 mst와는 무관한 문제이기에 mst로는 풀이하려는 것은 잘못된 접근이다.
• 자바에서 Priority Queue(pq)를 사용할 경우 C++와 다르게 디폴트값이 오름차순이기 때문에 pq에 값을 넣고 꺼낼 때 값을 음수화할 필요가 없다.

---

코드

import java.util.*;

public class Main {

    static class info implements Comparable<info> {
        int end, cost;

        info(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(info other) {
            return Integer.compare(this.cost, other.cost);
        }
    }

    static class vertax {
        int start, end;

        vertax(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    static Scanner scan = new Scanner(System.in);
    static final int INF = 987654321;
    static int n, m, a, b, c;
    static int[] d = new int[1001];
    static Vector<info>[] v = new Vector[1001];
    static Vector<vertax>[] nodes = new Vector[1001]; // 1부터 index까지 최단거리중 속하는 간선들 저장
    static boolean[][] visit = new boolean[1001][1001];
    static PriorityQueue<info> pq = new PriorityQueue<info>();
    static Vector<vertax> ans = new Vector<>();

    static void input() {
        n = scan.nextInt();
        m = scan.nextInt();
        for (int i = 1; i <= n; i++) {
            v[i] = new Vector<>();
            nodes[i] = new Vector<>();
            d[i] = INF;
        }
        for (int i = 0; i < m; i++) {
            a = scan.nextInt();
            b = scan.nextInt();
            c = scan.nextInt();

            v[a].add(new info(b, c));
            v[b].add(new info(a, c));

        }
    }

    static void solve() {

        d[1] = 0;
        pq.add(new info(1, 0));
        dijkstra();

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < nodes[i].size(); j++) {
                int start = nodes[i].get(j).start;
                int end = nodes[i].get(j).end;

                if(!visit[start][end]){
                    visit[start][end] = visit[end][start] = true;
                    ans.add(nodes[i].get(j));
                }
            }
        }

        System.out.println(ans.size());
        for(vertax i : ans){
            System.out.println(i.start + " " + i.end);
        }
    }

    static void dijkstra() {
        while (!pq.isEmpty()) {
            int cur = pq.peek().end;
            int cost = pq.peek().cost;
            pq.poll();

            for (info i : v[cur]) {
                int next = i.end;
                int next_cost = cost + i.cost;
                if (next_cost < d[next]) {
                    d[next] = next_cost;
                    nodes[next].clear();
                    nodes[next].addAll(nodes[cur]);
                    nodes[next].add(new vertax(cur, next));
                    pq.add(new info(next, next_cost));
                }
            }
        }
    }

    public static void main(String[] args) {

        input();
        solve();

    }
}

결론

문제 풀이 방법을 어떻게 생각하여 접근할지가 중요한 것 같다. 이 문제의 경우 만약 n의 범위가 작았다 하더라도 플로이드 와샬 알고리즘으로는 풀 수 없어 보인다. 최소 길이를 구하는 것이 아닌 간선들의 정보를 찾아야 하는 것이기 때문이다. 이와 같이 문제의 출력 조건도 잘 고려해보는 습관을 들이는 것이 좋을 것 같다.