본문 바로가기
코딩테스트

[최단경로] 백준 1504번 특정한 최단 경로 자바 (Java)

by Enhydra lutris 2023. 2. 3.

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

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node> {
    int end;
    int weight;

    Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }

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

}


public class No1504 {
    static int N, E;
    static int[] dist;
    static ArrayList<ArrayList<Node>> graph;
    static final int INF = 200000000;

    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 = new ArrayList<>();
        dist = new int[N + 1];

        //노드 초기화
        for (int i = 0; i <= N; i++)
            graph.add(new ArrayList<>());


        //값 입력 받고, 그래프에 초기화
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            //양방향 그래프를 만드는 부분
            graph.get(start).add(new Node(end, weight));
            graph.get(end).add(new Node(start, weight));
        }

        //반드시 거쳐야 하는 서로다른 정점 번호 받기
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        //꼭 방문해야하는 두정점을 방문하는 경우 두가지
        int case1 = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N); //1->v1->v2->N
        int case2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N);  //1->v2->v1->N

        //꼭 거쳐가야 하는 두정점을 방문하는 두가지 경우중 더 짧은 것 선택
        int result = (case1 >= INF && case2 >= INF) ? -1 : Math.min(case1, case2);
        System.out.println(result);
        br.close();

    }

    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        //배열 일괄 초기화
        Arrays.fill(dist, INF);

        //출발점 큐에 추가
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node nowNode = pq.poll();
            int now = nowNode.end; //큐에서 node 인스턴스 추출

            //최단 거리 구하는 로직
            for (Node node : graph.get(now)) {
                if (dist[node.end] > dist[now] + node.weight) {
                    dist[node.end] = dist[now] + node.weight;
                    pq.add(new Node(node.end, dist[node.end]));
                }
            }
        }
        return dist[end];
    }
}

풀이

해당 문제는 가중치 개념이 있는 최소경로값을 구하는 문제이므로 다익스트라를 이용하여 풀면 된다.

 

1753번 문제에 특정 정점을 반드시 지나야된다는 조건이 추가 된 문제이다.

https://seaotter.tistory.com/33

 

[최단경로] 백준 1753번 최단경로 자바 (Java)

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘

seaotter.tistory.com

 

특정 정점이 두개 이므로 정점을 지나는 방법은 아래와 같이 두가지이다.

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

이 두가지 케이스를 비교하여 더 짧은 것을 선택 하여 출력 하면 된다.

 

최단경로 푸는 방법

문제유형 푸는 방법
가중치 개념이 없는 최단 경로 문제 BFS
가중치 개념이 있는 한 노드 기준 최단 경로 문제 다익스트라
가중치 개념이 있는 여러 노드 기준 최단 경로 문제 플로이드 와샬

 

댓글