[JAVA] 백준 1504번 - 특정한 최단경로

<문제>

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

양방향 그래프에서 1번부터 N번까지 가는 최단거리를 구하려고 한다. 이때 반드시 주어진 2개의 정점은 지나야한다.

<입력>

#1: 정점 N, 간선 E (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
#2~E번반복: 정수 a,b,c - a에서 b까지 양방향 길, 거리가 c(1≤c≤1,000)
#마지막: 반드시 지나야 하는 서로 다른 두 정점 v1, v2(v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

<출력>

7

<풀이>

1~v1~v2~N OR 1~v2~v1~N
위의 2개 중에 최단 거리가 정답

• cost 초기값인 INF 는 오버플로우 나지 않도록 200,000(E의 최대값) * 1,000(c의 최대값) 값으로 설정
• 필요한 배열 및 리스트(모두 N(정점개수)+1로 초기화)
  • list: 정점 정보 저장(Node 타입의 ArrayList 이며 각 인덱스 안에도 새로운 ArrayList가 존재)
  • distance: 최단 거리 저장하는 배열(시작정점~i까지 거리)
  • visited: 방문했는지 확인하는 배열

1. 주어진 값들 입력받고 배열들 다 초기화
2. 주어진 a,b,c들 list에 추가(이때 양방향이므로 a,b모두 추가해야함!)
3. 1~v1~v2~N OR 1~v2~v1~N 두 가지 result들 중에 작은 값으로 판단해야함 (dijkstra 함수 호출)
4. dijkstra(start, end)
   • distance의 모든 값 INF로 초기화, visited 모든 값 false로 초기화, Node타입 우선순위큐(pq)생성
   • distance[start] = 0, pq에 (start,0)추가
   • pq가 비어있을 때까지 반복
     • pq에서 꺼내 현재 Node확인 후 현재의 도착점과 end가 같으면 중단(break)
     • 이후 방문(visited[])하지 않았다면 true(방문)으로 변경 / 방문 시 무시
     • list[end]의 사이즈만큼 반복
       • end의 값을 가져와 Node타입 node로 저장 - 다음꺼
       • if - 방문X && (현재 가중치+다음 가중치)<distance[] ⇒ 가중치들의 합을 distance[]에 저장, pq에 다음 노드 정보 저장
     • 반복이 끝나면 return - distance[end]
5. result1, result2가 모두 INF보다 크거나 같다면 경로가 없는 것이므로 -1출력
6. 아니라면 둘 중 Math.min으로 출력

=> 이 풀이대로 아래 코드를 작성하였다. 위의 풀이 순서대로 작성한 것이라 이해가 잘될 것이다.

<전체코드>

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

class Node implements Comparable<Node> {
    int end, weight;
    public Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node node) {
        return weight - node.weight;
    }
}
public class Main {
    static int N,E,result;
    static int INF = 200000000;
    static ArrayList<Node>[] list;
    static int[] distance;
    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()); //간선
        list = new ArrayList[N+1];
        distance = new int[N+1];
        visited = new boolean[N+1];

        for(int i=0; i<=N; i++)
            list[i] = new ArrayList<>();
        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());
            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        int result1 = 0;
        result1 = dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2,N);
        int result2 = 0;
        result2 = dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1,N);
        result = 0;
        if(result1>=INF && result2>=INF)
            result = -1;
        else
            result = Math.min(result1, result2);
        System.out.println(result);
    }
    public static int dijkstra(int start, int end) {
        Arrays.fill(distance, INF);
        Arrays.fill(visited, false);
        PriorityQueue<Node> pq = new PriorityQueue<>();
        distance[start] = 0;
        pq.add(new Node(start,0));
        while(!pq.isEmpty()) {
            Node current = pq.poll();
            if(current.end == end)
                break;
            if(visited[current.end]) continue;
            visited[current.end] = true;

            for(Node node : list[current.end]) {
                if(current.weight+node.weight < distance[node.end]) {
                    distance[node.end] = current.weight+node.weight;
                    pq.add(new Node(node.end, distance[node.end]));
                }
            }
        }
        return distance[end];
    }
}