[백준] 1504: 특정한 최단경로 (다익스트라 알고리즘) - JAVA

class 4

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

 

 

 

 

# 문제

방향성이 없는 그래프가 주어진다. 세준이는 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개 존재한다.

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

 

 

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

7

 

 

# 필요개념

이 문제를 풀 때, 신경써야 할 부분은 크게 두 가지였다.

• 무방향그래프이다 -> A노드와 B노드가 연결되어있고 가중치가 3이라면, A->B 의 가중치도 3이고 B->A의 가중치도 3이다. 이 두 가지 경우 모두 리스트에 넣어두어야 한다.
• 두 개의 점을 필수로 지난다. A와 B를 거쳐가야 한다면 아래의 두 경우로 나누어 쪼개 구해야 한다. 
  • 시작지점 -> A / A -> B / B -> 목표지점으로 가는 경우
  • 시작지점 -> B / B -> A / A -> 목표지점으로 가는 경우

 

우선 리스트 안에 리스트가 들어있는 구조로 만들었다. 1번노드에 3,4번 노드가 있다면 리스트 1번 인덱스에 리스트를 만들어 3,4번 노드를 넣어두는 식이다. 물론 무방향그래프임을 고려하여 3,4번 인덱스에도 1번노드를 넣어야 한다.

 

이후에는 다익스트라 알고리즘을 이용해 최소가중치를 구한다. 위에서 말했듯이 두가지 경우로 나누어 구해주었다. 여기서 find()는 다익스트라 알고리즘을 이용해 구현한 함수이다.

 

 

# Code

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

import static java.lang.Math.*;

public class Main {
    static List<List<E>> lst = new LinkedList<>();
    static boolean[] isVisit;
    static int[] dist;
    static final int MAX = 200000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        isVisit = new boolean[N + 1];
        dist = new int[N + 1];
        for (int i = 0 ; i <= N ; i++) {
            lst.add(new LinkedList<>());
        }

        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 distance = Integer.parseInt(st.nextToken());
            lst.get(start).add(new E(end, distance));
            lst.get(end).add(new E(start, distance));// 양방향이니까
        }
        st = new StringTokenizer(br.readLine());
        int nec1 = Integer.parseInt(st.nextToken());
        int nec2 = Integer.parseInt(st.nextToken());

        // start -> nec1 -> nec2 -> end 혹은 start -> nec2 -> nec1 -> end 이므로 끊어서 구하기
        int sol1 = 0;
        sol1 += find(1, nec1);
        sol1 += find(nec1, nec2);
        sol1 += find(nec2, N);

        int sol2 = 0;
        sol2 += find(1, nec2);
        sol2 += find(nec2, nec1);
        sol2 += find(nec1, N);

        int ans = 0;
        if (sol1 >= MAX && sol2 >= MAX) ans = -1;
        else ans = Math.min(sol1, sol2);
        System.out.println(ans);
    }

    private static int find(int start, int end) {
        Arrays.fill(dist, MAX);
        Arrays.fill(isVisit, false);

        PriorityQueue<E> queue = new PriorityQueue<>();
        queue.add(new E(start, 0));
        dist[start] = 0;
        while (!queue.isEmpty()) {
            E nowNode = queue.poll();
            int location = nowNode.end;

            if (!isVisit[location]) {
                isVisit[location] = true;

                for (E node : lst.get(location)) {
                    if (!isVisit[node.end] && dist[node.end] > dist[location] + node.distance) {
                        dist[node.end] = dist[location] + node.distance;
                        queue.add(new E(node.end, dist[node.end]));
                    }
                }
            }
        }
        return dist[end];
    }
}
class E implements Comparable<E>{
    int end;
    int distance;

    public E(int e, int d) {
        this.end = e;
        this.distance = d;
    }

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

 

 

# 결과