백준 1854번 : K번째 최단경로 찾기 [Java]

문제

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

1854번: K번째 최단경로 찾기

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class Node implements Comparable<Node> {
        int idx;
        int value;

        public Node(int idx, int value) {
            super();
            this.idx = idx;
            this.value = value;
        }

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

    static List<Node>[] graph;
    static PriorityQueue<Integer>[] dist;
    static int n, m, k;
    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());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        graph = new ArrayList[n + 1];
        Comparator<Integer> cp = new Comparator<Integer>() {
        	public int compare(Integer o1, Integer o2) {
        		return o1 < o2 ? 1 : -1;
        	}
        };
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            graph[start].add(new Node(end, value));
        }
        dist = new PriorityQueue[n + 1];
        for (int i = 1; i <= n; i++) {
            dist[i] = new PriorityQueue<>(k, cp);
        }
        dijkstra();
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            // k찾기
            if (dist[i].size() == k) {
                sb.append(dist[i].peek()).append("\n");
            }
            else {
            	sb.append(-1).append("\n");
            }
        }
        System.out.println(sb);
    }

    static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        dist[1].add(0);
        while (!pq.isEmpty()) {
            Node now = pq.poll();
            for (Node next : graph[now.idx]) {
            	if(dist[next.idx].size() < k) {
            		dist[next.idx].add(now.value + next.value);
            		pq.add(new Node(next.idx, now.value + next.value));
            	}
            	else if(dist[next.idx].peek() > now.value + next.value) {
            		dist[next.idx].poll();
            		dist[next.idx].add(now.value + next.value);
            		pq.add(new Node(next.idx, now.value + next.value));
            	}
            }
        }
    }
}

 

접근방법

처음에는 평범한 다익스트라 문제라고 생각했는데 너무너무너무 어려웠다...

일단 처음에 생각했던 방법은 k번째를 찾기 위해서 다익스트라 과정에서 최소값을 찾는게 아니라 찾아지는 거리 List<Integer>배열을 만들어서 저장했다.

visited를 boolean이 아니라 int로 선언하고 입력 받을 때 진입차수를 따로 저장했다.

그리고 특정 지점에 방문할 때 마다 visited를 증가 시켜서 진입차수 만큼 될때까지 방문 했다.

탐색을 마친 후에 list의 사이즈를 측정해서 k보다 작으면 -1을 출력하고

k이상이면 배열을 정렬한 후에 k번째 수를 찾아서 출력했다.

이렇게 하면 예제 테케는 맞게 된다.

 

하지만 내가 간과 했던 조건 두가지가 있다.

• i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 
• 최단경로에 같은 정점이 여러 번 포함되어도 된다.

문제에 떡하니 적혀 있던 부분인데 이걸 그냥 스루했다.

만약에 사이클이 존재하는 그래프라면 다시 나를 방문하는 것도 가능하고 아무튼 들렀다 올 수 있는 모든 곳을 여러번 갔다오는 것도 가능하다.

visited를 처음에 했던 방법으로 하게 되면

1-2-3 이런 경로가 있을때 3에 대한 진입차수가 1이라면 이 경우 밖에 안본다

1-2-4-5-2-3 하지만 이런 식으로 2와 3사이에 다른데를 더 방문하고 2에 다시 방문했다가 돌아오는 경우를 고려하지 못하게 되기 때문에 visited를 삭제 해주었다.

거리 리스트를 우선순위 큐 배열로 변경해주고 큐 사이즈가 k보다 커지면 맨 앞에 있는 값과 현재 길이를 비교하여 현재 길이로 맨 앞에 있는 값을 변경 해주었다.

 

오늘의 교훈

문제 조건을 놓치지말고 꼼꼼히 다 보도록 하자.