[백준 1504번 / Java] 특정한 최단 경로 - 다익스트라(Dijkstra)

문제 링크

Gold 4

 

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

1504번: 특정한 최단 경로

 

https://mag1c.tistory.com/452

다익스트라(Dijkstra) 알고리즘

 

 

풀이

방향성이 없는 그래프가 주어졌으며, 이는 양방향으로 구현해야 함

또한 주어진 두 가지의 경로 v1, v2를 모두 통과한 후 최종 지점으로 도착할 수 있는 경로를 구해야한다는 점이다.

 

1번에서 출발해서 v1, v2를 거쳐 최종 목적지로 도착하는 방법은 두 가지가 있으며 이를 쪼개면 다음과 같이 표현할 수 있다.

1 → v1 → v2 → goal
// 1 → v1
// v1 → v2
// v2 → goal

1 → v2 → v1 → goal
// 1 → v2
// v2 → v1
// v1 → goal

 

위에서 종합한 조건들을 바탕으로 기본 다익스트라 알고리즘을 구현한 코드 위에 아래 세 가지만 고려하여 작성하면 된다.

 

1. 양방향으로 구현하기 때문에 반대의 경우도 노드 리스트에 추가

for(int i = 0; i < E; i ++) {
    st = new StringTokenizer(br.readLine(), " ");
    int before = Integer.parseInt(st.nextToken());
    int after = Integer.parseInt(st.nextToken());
    int weight = Integer.parseInt(st.nextToken());

    //단방향
    nodeList.get(before).add(new Node(after, weight));
    
    //양방향
    nodeList.get(after).add(new Node(before, weight));
}

 

2. 파라미터로 각 조건을 분할해서 수행하면 코드의 재사용성을 극대화할 수 있음

int distV1 = 0;
distV1 += dist(1, v1);
distV1 += dist(v1, v2);
distV1 += dist(v2, N);

int distV2 = 0;
distV2 += dist(1, v2);
distV2 += dist(v2, v1);
distV2 += dist(v1, N);

private static int dist(int start, int end) {
	//코드
}

 

3. Integer.MAX_VALUE로 초기화한 기존 dist배열을 문제 조건에 맞게. 간선 개수(200,000) * 거리(1000)의 최대 값인 2억개로 셋팅해준다.

private static int INF = 200000000;
Arrays.fill(dist, INF);

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int N;
    private static int E;
    private static int v1;
    private static int v2;
    private static int[] dist;
    private static boolean[] visited;
    private static List<List<Node>> nodeList = new ArrayList<>();
    private static int INF = 200000000;

    static class Node implements Comparable<Node> {
        int node;
        int cost;

        public Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return cost - o.cost;
        }
    }

    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());

        for(int i = 0; i <= N; i ++) {
            nodeList.add(new ArrayList<>());
        }

        for(int i = 0; i < E; i ++) {
            st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            nodeList.get(before).add(new Node(after, weight));
            nodeList.get(after).add(new Node(before, weight));
        }

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

        dist = new int[N + 1];
        visited = new boolean[N + 1];

        int distV1 = 0;
        distV1 += dist(1, v1);
        distV1 += dist(v1, v2);
        distV1 += dist(v2, N);

        int distV2 = 0;
        distV2 += dist(1, v2);
        distV2 += dist(v2, v1);
        distV2 += dist(v1, N);

        System.out.println(distV1 >= INF && distV2 >= INF ? -1 : Math.min(distV1, distV2));
    }

    private static int dist(int start, int end) {
        Arrays.fill(dist, INF);
        Arrays.fill(visited, false);
        dist[start] = 0;

        PriorityQueue<Node> nodeQueue = new PriorityQueue<>();
        nodeQueue.offer(new Node(start, 0));

        while (!nodeQueue.isEmpty()) {
            Node curNode = nodeQueue.poll();
            int cur = curNode.node;

            if(!visited[cur]) {
                visited[cur] = true;

                for(Node node : nodeList.get(cur)) {
                    if(!visited[node.node] && dist[node.node] > dist[cur] + node.cost) {
                        dist[node.node] = dist[cur] + node.cost;
                        nodeQueue.offer(new Node(node.node, dist[node.node]));
                    }
                }
            }
        }
        return dist[end];
    }
}