백준[자바]_9370_미확인도착지_다익스트라

한동안 미뤄두었던 최단거리 알고리즘 문제를 풀어보았다. 오랜만에 풀어보다 보니 많은 난항을 겪었는데, 풀이과정과 접근 방법을 정리해보겠다. 

시작노드에서 도착노드까지의 최단거리가 구해지는 것은 맞는데, 최단거리를 구성하는 경로의 경우의 수가 반드시 하나일 것이라는 보장이 없다. 바로 전전 단계 문제인 특정한 최단 경로와 아주 비슷한 문제라고 생각할 수 있다.

[ 접근 1 ]

이전에 다익스트라 문제를 풀어보았을 때, 특정 정점을 지나서 가는 경로를 구하는 문제를 풀어본 적이 있었다. 단순하게 생각해서 정점 g, h를 연결하는 경로를 반드시 지나가야 할때, 시작노드가 s, 도착노드가 e라고 하면, s -> e인 최단 거리가  s -> g -> h -> e인 경우에 구해지는 최단 거리 또는 s -> h -> g -> e인 경우에 구해지는 최단 거리와 같은 경우 e는 문제에 조건을 만족한다는 의미로 해석할 수 있다. 하지만 이는 적어도 다익스트라를 세번 호출해서 비교를 해주어야 하기 때문에 보류하고 1번의 호출로 해결할 수 있는 방법을 고민해보았다. 

 

[ 접근 2 ]

주어진 간선의 가중치 값에 약간의 변형을 주어서 특정 경로(간선)를 이동했는지 여부를 확인해볼 수 있다. 예를 들어 모든 가중치에 2를 곱하면 값은 반드시 짝수가 된다. 그 중에서 문제에서 주어진 특정한 경로만 -1을 해서 홀수를 만들어 준다.   1정도는 빼더라도 모든 값을 비슷한 비율로 변경했기 때문에 충분히 무시할 만큼 작다. 

자 여기서 문제에서 주어진 후보 노드의 최단거리가 짝수라면? 특정 경로를 지나지 않은 것이고, 홀수라면 지난것이다. 

간단하게 생각해서 보면 (짝수 + 짝수)는 몇번을 더하던 짝수가 나온다. 하지만 이 중에 홀수가 하나라도 포함되면 합의 결과는 홀수가 나온다.(한번 방문한 정점은 방문하지 않으므로 홀수 + 홀수는 생각하지 않아도 된다.) 따라서 최단거리가 홀수라는 말은 짝수들의 합 중에서 단 하나의 홀수가 더해졌다는 것이고, 이 말은 특정 경로를 지나서 최단거리를 이동했다는 것이다. 

추가로 필자가 처음 이야기 했던 대로, 특정 경로를 지나면서 최단거리를 구하는 경우의 수가 하나 라는 것을 보장할 수 없다. 이를 해결해줄 작업이 한 가지 필요한 데, 방문체크를 좀 더 엄격하게 해주는 것이다. 

원래 기존의 다익스트라 알고리즘은 다음과 같다. 

1. 노드의 값을 우선 순위 큐에 넣는다.
2. 방문 확인&체크를 한다. (큐에 같은 값이 반복적으로 들어오더라도 우선순위가 되어 나온 값이 이미 방문한 곳이라면 여기서 걸러주는 것이다. -> 이 부분에서 경우의 수가 발생한다.
3. 큐에서 노드를 꺼내고 해당 노드의 인접 노드를 탐색한다. 
4. 최단 거리가 갱신된다면 갱신하고 아니면 넘어간다. 
5. 1~4의 과정을 우선순위큐에 값이 없을때 까지 반복한다.

이를 해결하는 방법은 4번 과정에서 방문 확인을 한 번 더 해주도록 수정해주는 것이다. 즉 

아직 방문한 적이 없고, 최단 거리가 갱신될 수 있는 조건을 만족하는 경우에만 최단거리를 갱신하면서 탐색을 이어 나가는 것이다. 이렇게 하면 무방향 그래프이기 때문에 결국 모든 노드를 탐색할 수 있고, 최단거리를 구하는 경우의 수가 하나로 고정할 수 있다.

언제든지 필자의 설명이 부족하거나, 잘못된 개념을 알고 있는 것을 보신다면 감사하게 피드백을 받겠다.

package Dijkstra;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class _9370_미확인도착지_100 {
    static int min_dist[];
    static int n,m,t, T;
    static List<List<Node9370>> list;
    static boolean visit[];
    static final int INF = 100000000;
    static class Node9370 implements Comparable<Node9370>{
        int node, weight;
 
        public Node9370(int node, int weight) {
            super();
            this.node = node;
            this.weight = weight;
        }
        //우선 순위큐의 정렬 기준(우선순위 기준) 제공. -> 오름차순 정렬 작은 것 먼저(최단거리) -> 최소 힙 
        @Override
        public int compareTo(Node9370 o) {
            // TODO Auto-generated method stub
            return this.weight - o.weight;
        }
    }
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        //테스트케이스 수
        T = Integer.parseInt(br.readLine());
        
        while(T-->0) {
            st = new StringTokenizer(br.readLine());
            //교차로의 개수 = 정점 개수
            n = Integer.parseInt(st.nextToken());
            //도로의 개수   = 간선 개수
            m = Integer.parseInt(st.nextToken());
            //목적지 후보의 개수
            t = Integer.parseInt(st.nextToken());
            
            //최단거리 배열
            min_dist = new int[n+1];
            //최단 거리 배열 초기화 (차후에 시작노드는 0으로 초기화)
            Arrays.fill(min_dist, INF);
            
            //인접 리스트 생성
            list = new ArrayList<>(n+1);
            //인접 리스트 초기화
            for(int i=0; i<=n; i++) {
                list.add(new ArrayList<>());
            }
            
            st = new StringTokenizer(br.readLine());
            //예술가듀오의 출발 노드
            int s = Integer.parseInt(st.nextToken());
            //예술가 듀오가 확실히 지나가는 두 정점
            int g = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            
            //인접리스트에 간선 정보 초기화 
            for(int i=0; i<m; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                
                //두 정점 a, b사이의 가중치
                int d = Integer.parseInt(st.nextToken());
                
                if((a==g && b ==h) || (a==h && b == g)) {//반드시 지나는 정점은 홀수로
                    list.get(a).add(new Node9370(b, d*2-1));
                    list.get(b).add(new Node9370(a, d*2-1));
                }else {
                    list.get(a).add(new Node9370(b, d*2));
                    list.get(b).add(new Node9370(a, d*2));
                }
            }
            
            //후보 정점
            List<Integer> target = new ArrayList<Integer>();
            for(int k=0; k<t; k++) {
                target.add(Integer.parseInt(br.readLine()));
            }
            
            dijkstra(s);
            
            Collections.sort(target);
            
            for(int num : target) {
                if(min_dist[num] % 2 == 1) {
                    sb.append(num).append(' ');
                }
            }
            sb.append('\n');
            
        }//end-while-t
        
        System.out.println(sb);
        
    }
    private static void dijkstra(int start) {
        // TODO Auto-generated method stub
        //방문 배열
        visit = new boolean[n+1];
        //다익스트라 알고리즘 시작
        PriorityQueue<Node9370> pq = new PriorityQueue<Node9370>();
        //시작노드와 거리값을 초기화(시작노드의 최단거리배열은 0)
        min_dist[start] = 0;
        pq.add(new Node9370(start, 0));
        
        while(!pq.isEmpty()) {
            Node9370 currentNode = pq.poll();
            
            if(visit[currentNode.node]) continue;
            //방문 처리
            visit[currentNode.node] = true;
            
            //현재 노드에서 인접 노드를 탐색
            for(Node9370 node : list.get(currentNode.node)) {
                
                //최단거리 배열 업데이트 하기 
                if(!visit[node.node] && min_dist[node.node] > min_dist[currentNode.node] + node.weight) {
                    min_dist[node.node] = min_dist[currentNode.node] + node.weight;
                    pq.add(new Node9370(node.node, min_dist[node.node]));
                }
            }
        }
    }
}