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

📖 문제

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

 

 

 

💡  풀이 방식

• 다익스트라

필요 자료구조
- 인접 배열 리스트
- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열
- N개의 각 정점에 대한 boolean형 방문 표시 배열
- (목적지, 거리) 정보를 저장하는 객체

 

 

1. E개의 입력을 받으며 두 정점 간 거리 정보를 양방향으로 저장한다.

2. 꼭 지나쳐야 하는 두 정점 v1, v2를 입력받는다.

3. ① 경로 1 > v1 > v2 > N을 지날 때의 최단 거리와, ② 경로 1 > v2 > v1 > N을 지날 때의 최단거리를 계산한다. (다익스트라)

4. 두 최단 거리가 모두 최댓값인 INF보다 크거나 같으면, 경로가 없는 것이므로 -1을 출력하고, 그게 아니라면 경로 1의 최단 거리와 경로 2의 최단 경로 길이 중 최솟값을 정답으로 출력한다.

 

 

 

 

💥 유의사항

최단 거리 배열 dist를 채우는 초기값은 20,000,000 (= 간선의 갯수 E의 최댓값 20만 * 두 정점 간 최대 거리 1000)으로 설정한다.

Integer.MAX_VALUE로 했다간 오버플로우가 발생할 수 있다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int INF = 200000*100;    // 간선 최대 개수 E * 가중치 최댓값 c
    
    static int N,E;
    static List<Node>[] list;
    static int[] dist;  // 시작점에서 각 정점으로 가는 최단 거리
    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];
        for(int i = 1 ; i <= N ; i++)   list[i] = new ArrayList<>();
        
        dist = new int[N+1];
        visited = new boolean[N+1];
        
        while(E --> 0) {
            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());
        
        // 경로1) 1 > v1 > v2 > N
        int ans1 = 0;
        ans1 += dijkstra(1, v1);
        ans1 += dijkstra(v1, v2);
        ans1 += dijkstra(v2, N);
        
        // 경로2) 1 > v2 > v1 > N
        int ans2 = 0;
        ans2 += dijkstra(1, v2);
        ans2 += dijkstra(v2, v1);
        ans2 += dijkstra(v1, N);
        
        int answer = 0;
        answer = (ans1 >= INF && ans2 >= INF) ? -1 : Math.min(ans1, ans2);
        System.out.println(answer);
    }
    
    // [다익스트라]
    private static int dijkstra(int start, int end) {
        // 방문 표시 배열과 거리 배열은 매번 초기화하기 !!
        Arrays.fill(visited, false);
        Arrays.fill(dist, INF);
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        dist[start] = 0;    // 시작점 거리 0으로 세팅
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            
            if(visited[now.e])  continue;   // 방문했던 정점은 pass
            visited[now.e] = true;
            
            // 현재 노드에 연결된 다른 노드 탐색
            for(Node next : list[now.e]) {
                if(dist[next.e] > now.v + next.v) { // 더 작은 경로로 이동
                    dist[next.e] = now.v + next.v;
                    pq.add(new Node(next.e, dist[next.e]));
                }
            }
        }
        
        return dist[end];   // 목적지 end까지의 최단 거리
    }
}
 
class Node implements Comparable<Node> {
    int e, v;   // 목적지, 거리
    
    public Node(int e, int v) {
        this.e = e;
        this.v = v;
    }
    
    // 거리 기준 오름차순 정렬
    @Override
    public int compareTo(Node n) {
        return this.v - n.v;
    }
}

 

 

➕ 다른 풀이 방식

더 작은 경로로 이동하도록 갱신하는 코드 부분이 약간 다르다.

[다익스트라] 백준 1504번 특정한 최단 경로 - JAVA

if(dist[next.e] > dist[now.e] + next.v) {
	dist[next.e] = dist[now.e] + next.v;
    pq.add(new Node(next.e, dist[next.e]));
}

 

---

💦 어려웠던 점

- 다익스트라를 잊고 있었다,,

- 그래도 우선순위 큐 쓸 생각은 들었다!

- 1>v1>v2>N으로 가는 경로와 1>v2>v1>N으로 가는 경로의 최단 길이를 구할 생각을 하지 못 했다.

 

🧐 새로 알게 된 내용

- 잊고 있던 다익스트라 상기시키기,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 1504번 특정한 최단 경로 (JAVA)

 

[BOJ] 백준 1504번 : 특정한 최단 경로 (JAVA)