[Java] 1504번 특정한 최단 경로 문제 해설

문제 풀이 원본

[문제 풀이] 해당 문제는 양방향의 길을 통해 최단 거리를 구하는 문제이다. 추가적으로 1번째 점에서 N번째 점으로 도달하는 과정에서 2개의 점을 무조건 경유해서 도착해야 한다는 조건을 가진다.

조건을 보면 까다로워 보일 수 있으나 두 점을 경유하며 지정한 위치로 최단 거리로 가는 경우의 수를 생각하면 쉽게 구할 수 있다.

두 점을 경유하며 목적지로 가는 방법은 두가지 뿐이다.

출발지 -> 목적지 1 -> 목적지 2 -> 도착지
출발지 -> 목적지 2 -> 목적지 1 -> 도착지

위 과정에서 각 점과 점 사이의 거리는 다익스트라(테이크스트라) 알고리즘을 사용하면 쉽게 구할 수 있다. 다익스트라 알고리즘에 대한 자세한 설명은 아래 포스팅을 확인하면 이해하기 좋을 것 같다.

2023.07.22 - [algorithm/theory] - 다익스트라(Dijkstra) 알고리즘

출발지에서 모든 점까지의 최단거리, 목적지 1에서 모든 점까지의 최단거리, 목적지 2에서 모든 점까지의 최단거리 총 3번의 다익스트라 알고리즘을 사용하여 구하고, 위 두가지 방법 중 짧은 거리를 출력하면 정답으로 나온다.

이 때 만약 도달할 수 없다면(최단 거리가 INF보다 높을 경우, INF는 무한) -1을 출력하는 예외 처리를 해주어야 한다.

[코드 풀이] 문제를 풀면서 각 점까지의 거리의 최소를 쉽게 구하기 위해 Point class를 구현하여 사용하였다.

public static class Point implements Comparable<Point>{
        int index;
        int distance;

        public Point(int index, int distace) {
            this.index = index;
            this.distance = distace;
        }

        @Override
        public int compareTo(Point o) {
            return this.distance - o.distance;
        }
    }

구현을 하며 우선순위 큐(PriorityQueue)에서 거리의 최소를 구하기 위해 compareTo를 구현하여 거리가 작은 순으로 배열할 수 있도록 했다.

다음으로는 원하는 점에서 최단 거리를 구하는 Dijkstra 메서드를 구현하였다.

public static int[] dijkstra(int start) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N+1];
        int[] dp = new int[N+1];
        Arrays.fill(dp, INF);

        pq.add(new Point(start, 0));
        dp[start] = 0;

        while(!pq.isEmpty()) {
            Point pos = pq.poll();

            int to = pos.index;

            if(visited[to]) continue;

            visited[to] = true;

            for(Point next : route.get(to)) {
                if(dp[to] + next.distance < dp[next.index]) {
                    dp[next.index] = dp[to] + next.distance;
                    pq.add(new Point(next.index, dp[next.index]));
                }
            }
        }

        return dp;
    }

정답 코드는 아래와 같다.

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

public class Main {

    public static class Point implements Comparable<Point>{

        int index;
        int distance;

        public Point(int index, int distace) {
            this.index = index;
            this.distance = distace;
        }
        @Override
        public int compareTo(Point o) {
            return this.distance - o.distance;
        }
    }

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int INF = 100_000_000;

    public static int N;
    public static int E;

    public static ArrayList<ArrayList<Point>> route;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        N = Integer.parseInt(st.nextToken()); 
        E = Integer.parseInt(st.nextToken());

        int point1 = 0;
        int point2 = 0;

        route = new ArrayList<ArrayList<Point>>();

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

        for(int i = 0; i < E; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine()," ");

            point1 = Integer.parseInt(st1.nextToken());
            point2 = Integer.parseInt(st1.nextToken());
            int distance = Integer.parseInt(st1.nextToken());

            route.get(point1).add(new Point(point2,distance));
            route.get(point2).add(new Point(point1,distance));
        }

        StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
        int target1 = Integer.parseInt(st2.nextToken());
        int target2 = Integer.parseInt(st2.nextToken());

        int[] startAtS = dijkstra(1);
        int[] startAt1 = dijkstra(target1);
        int[] startAt2 = dijkstra(target2);

        int sum1 = startAtS[target1] + startAt1[target2] + startAt2[N];
        int sum2 = startAtS[target2] + startAt2[target1] + startAt1[N];

        int min = Math.min(sum1, sum2);

        if(min >= INF)
            System.out.println("-1");
        else
            System.out.println(min);
    }

    public static int[] dijkstra(int start) {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N+1];
        int[] dp = new int[N+1];
        Arrays.fill(dp, INF);

        pq.add(new Point(start, 0));
        dp[start] = 0;

        while(!pq.isEmpty()) {
            Point pos = pq.poll();

            int to = pos.index;

            if(visited[to]) continue;

            visited[to] = true;

            for(Point next : route.get(to)) {
                if(dp[to] + next.distance < dp[next.index]) {
                    dp[next.index] = dp[to] + next.distance;
                    pq.add(new Point(next.index, dp[next.index]));
                }
            }
        }

        return dp;
    }

}

SSAFY10-Class5-Algorithm / BOJ

[Java] 1504번 특정한 최단 경로 문제 해설 #4

문제 풀이 원본