백준 1719 택배(JAVA)

 

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

1719번: 택배

 

문제 풀이

이 문제를 보고 바로 떠올린 것은 폴로이드 워샬 알고리즘이었다. 하지만, 폴로이드 워샬을 썼을 때 첫번째 경유지를 어떻게 처리해야할지 고민하고 있었는데, 이 문제의 범위를 보니 시간 복잡도 O(E log V) 다익스트라 알고리즘으로 풀릴거라 생각이 들었다.

먼저 Node 클래스를 정의해 다음 정점과 가중치, 처음으로 들렸던 정점을 정의해주었다.

static class Node implements Comparable<Node>{
        int next;
        int value;
        int first;

        public Node(int next, int value, int first){
            this.next = next;
            this.value = value;
            this.first = first;
        }
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }

 

그리고 first로 진행해왔던 경로에서 첫번째로 들렀던 곳을 저장해서 기본 다익스트라 가중치 비교에서 가중치가 바뀔때,

first가 0인지 0이 아닌지를 판단만하면 된다.

for(Node next: list[now.next]){
                if(w[next.next] > w[now.next] + next.value){
                    w[next.next] = w[now.next] + next.value;
                    if(now.first == 0){
                        result[start][next.next] = next.next;
                        queue.add(new Node(next.next, w[next.next], next.next));
                    }
                    else{
                        result[start][next.next] = now.first;
                        queue.add(new Node(next.next, w[next.next], now.first));
                    }
                }
            }

 

전체 코드

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


public class Main {
    static class Node implements Comparable<Node>{
        int next;
        int value;
        int first;

        public Node(int next, int value, int first){
            this.next = next;
            this.value = value;
            this.first = first;
        }
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }
    static List<Node> list[];
    static boolean visited[];
    static int result[][];
    static int w[];
    static int INF = Integer.MAX_VALUE;

    static void Dekkstra(int start){
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start,0,0));

        while (!queue.isEmpty()){
            Node now = queue.poll();

            if(visited[now.next]) continue;
            visited[now.next] = true;

            for(Node next: list[now.next]){
                if(w[next.next] > w[now.next] + next.value){
                    w[next.next] = w[now.next] + next.value;
                    if(now.first == 0){
                        result[start][next.next] = next.next;
                        queue.add(new Node(next.next, w[next.next], next.next));
                    }
                    else{
                        result[start][next.next] = now.first;
                        queue.add(new Node(next.next, w[next.next], now.first));
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        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());
        result = new int[n + 1][n + 1];
        list = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        w = new int[n + 1];
        Arrays.fill(w,INF);
        for(int i = 1; i<=n;i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list[a].add(new Node(b,c,0));
            list[b].add(new Node(a,c,0));
        }

        for(int i = 1;i<=n;i++){
            Dekkstra(i);
            visited = new boolean[n + 1];
            w = new int[n + 1];
            Arrays.fill(w,INF);
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(i == j) System.out.print("- ");
                else System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }
}