1504번

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

1504번: 특정한 최단 경로

오늘도 한 감자 했다...어제와 비슷한 문제였는데...문제를 좀만 더 잘 읽을걸 그랬다.

문제의 내용은 간단하다 주어지는 특정한 정점 두개를 반드시 지나는 최단경로를 구하라는 것이다.

여기서 내가 실수 한 것은 문제에서 양방향의 간선이 주어졌다는 것이다....저번 1753번 문제를 생각하면서 풀다보니...양방향은 생각도 못했다....그래서 몇 시간 동안 뭔 난리를 친건지...그래서 결과 적으로 양방향의 간선을 넣어주자마자 통과했다.

 

이 문제의 풀이 방법은 간단하다. 주어지는 특정정점들까지의 최단경로를 다익스트라로 탐색하고 이 것들의 합을 구하는 것이다.

식으로 설명하자면, f(a,b)라는 a에서 b로 가는 최단경로를 찾는 다익스트라 알고리즘 함수가 있다고 했을 때,

f(1,a)+f(a,b)+f(b,N)과 f(1,b)+f(b,a)+f(a,N)의 값중에 작은 값을 고르는 것이다.

위 식은 1-a-b-N, 1-b-a-N의 두 가지 경로를 의미한다.

그리고 만약 위의 탐색에서 특정 노드에 접근 하는 경로가 없으면 -1로 반환하면 된다.

나머지는 여러글에서 올라오듯 다익스트라 알고리즘 그대로이다.

 

나의 경우에는 Graph클래스를 정의해서 findMin메서드로 최단 경로를 반환하게 만들었다.

여기서 중요한 것은 우선순위 큐를 사용하는 것이다.

 

정답 코드는 아래와 같다.

 

package backjoon.b1504;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.io.*;
import java.util.*;
public class b1504 {
    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());
        Graph g = new Graph(N);
        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            g.addEdge(u,v,w);//간선 추가
        }
        st = new StringTokenizer(br.readLine());
        int node1 = Integer.parseInt(st.nextToken());
        int node2 = Integer.parseInt(st.nextToken());
        int min=g.findMin(node1,node2);//최단경로 반환

        System.out.println(min);
    }
}
class Graph{
    int N;
    LinkedList<Node>[] adj;
    PriorityQueue<Node> queue;
    int[] distance;
    public Graph(int N){
        this.N = N;
        adj = new LinkedList[N+1];
        for(int i=0; i<=N; i++){
            adj[i]=new LinkedList<>();
        }
        queue = new PriorityQueue<>();
        distance = new int[N+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
    }
    public void addEdge(int u, int v, int w){
        adj[u].add(new Node(v,w));
        adj[v].add(new Node(u,w));
    }
    public int bfs(int start, int end){
        Arrays.fill(distance,Integer.MAX_VALUE);//각각의 경로 탐색과정(bfs(1,node1),bfs(node1,node2)...)에 이전 탐색이 영향을 주지 않기 위해서 초기화한다.
        queue.add(new Node(start,0));
        distance[start]=0;
        while (!queue.isEmpty()){
            Node node = queue.poll();

            if(node.weight>distance[node.end])continue;

            for (Node nextNode : adj[node.end]) {
                int dis = node.weight+nextNode.weight;//현재 노드의 누적된 가중치와 다음 노드의 가중치를 더한 값
                if(dis<distance[nextNode.end]){//다음 노드의 저장되어있는 누적 가중치와 현재 다른 경로로 구한 가중치를 비교
                    distance[nextNode.end]=dis;
                    queue.add(new Node(nextNode.end, dis));
                }
            }
        }
        return distance[end];
    }
    public int findMin(int node1,int node2){
        int min = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        if(bfs(1, node1)<Integer.MAX_VALUE && bfs(node1, node2)<Integer.MAX_VALUE && bfs(node2, N)<Integer.MAX_VALUE){
            min = bfs(1, node1) + bfs(node1, node2) + bfs(node2, N);
        }
        if ((bfs(1, node2)<Integer.MAX_VALUE && bfs(node2, node1)<Integer.MAX_VALUE && bfs(node1, N)<Integer.MAX_VALUE)) {
            min2= bfs(1, node2) + bfs(node2, node1) + bfs(node1, N);
        }
        if(min==Integer.MAX_VALUE && min2==Integer.MAX_VALUE){
            return -1;
        }//특정 노드에 접근할 수 없을 때 -1 반환
        return Math.min(min,min2);
    }// 1-a-b-N, 1-b-a-N의 경로 중 최단 경로 반환
}
class Node implements Comparable<Node>{
    int weight;
    int end;

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

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.weight,o.weight);
    }
}