문제 바로가기

나의 풀이

다익스트라를 2번 써주는 문제이다. 다만 문제를 풀다보니 스스로 너무 많은 생각을 해서 오히려 시간을 많이 써버렸다.

내가 착각한 것은 start - v1 - v2 - end 경우와 start - v2 - v1 - end 경우 뿐만 아니라 start - v1 - v2 - v1 - end 와 같이 다시 되돌아가는 경우까지 고려해줘야 하지 않을까? 였다.

이것을 고려하기 위해 각각의 경우가 INF 인 경우... 등을 if 문으로 처리하고.. 여튼 결과적으로는 필요없는 짓이다. v2에서 end로 직접적으로 가는 길이 없더라도 다익스트라를 통해 v2는 v1을 거쳐서 가는 최단경로가 존재한다면 그 값을 dist 배열에 담아보낼 것이기 때문이다.

또한 주의해야할 점이 다익스트라를 2번 돌리기 위해 dist 배열과 visited 배열은 그냥 다익스트라 메서드 내에서 초기화되게 하는 것이 낫다. 그리고 편의상 배열 길이를 하나 늘려서 선언하여 노드의 숫자 자체를 인덱스로 하는 경우, start가 인덱스 0이 아니고 1임을 꼭 명심하자!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// graph 배열의 리스트에 추가할 노드
class Node implements Comparable<Node> {
    // 이어진 노드 x
    public int x;
    // 거리 비용 w
    public int w;

    public Node(int x, int w) {
        this.x = x;
        this.w = w;
    }
    
    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.w, o.w);
    }
}

class Main {

    static int INF = 200000000;
    static int n, e;
    // Node 담을 리스트가 여러개 있는 graph 선언
    static List<Node>[] graph;
    static int[] dist;
    static boolean[] visited;

    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());
        e = Integer.parseInt(st.nextToken());
        
        // graph 초기화
        graph = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 양방향이므로 a, b 각자 add 하기
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a].add(new Node(b, c));
            graph[b].add(new Node(a, c));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        // v1에서 출발하는 경우
        dijkstra(v1);
        int start_v1 = dist[1];
        int v1_v2 = dist[v2];
        int v1_end = dist[n];

        // v2에서 출발하는 경우
        dijkstra(v2);
        int start_v2 = dist[1];
        int v2_v1 = dist[v1];
        int v2_end = dist[n];

        int ans1 = start_v1 + v1_v2 + v2_end;
        int ans2 = start_v2 + v2_v1 + v1_end;
        if (ans1 >= INF && ans2 >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(Math.min(ans1, ans2));
        }
    }

    public static void dijkstra(int start) {
        dist = new int[n + 1];
        visited = new boolean[n + 1];
        Queue<Node> q = new PriorityQueue<>();
        Arrays.fill(dist, INF);
        q.offer(new Node(start, 0));
        dist[start] = 0;
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (visited[node.x]) continue;
            else visited[node.x] = true;
            for (Node next : graph[node.x]) {
                if (dist[next.x] >= dist[node.x] + next.w) {
                    dist[next.x] = dist[node.x] + next.w;
                    q.add(new Node(next.x, dist[next.x]));
                }
            }
        }
    }
}