문제

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

입력

첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 250\,000$, $1 ≤ k ≤ 100$, $mk ≤ 3\,000\,000$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 $m$개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 $a$, $b$, $c$가 포함되어 있다. 이것은 $a$번 도시에서 $b$번 도시로 갈 때는 $c$의 시간이 걸린다는 의미이다. ($1 ≤ a, b ≤ n$, $1 ≤ c ≤ 1\,000$)

도시의 번호는 $1$번부터 $n$번까지 연속하여 붙어 있으며, $1$번 도시는 시작도시이다. 두 도로의 시작점과 도착점이 모두 같은 경우는 없다.

출력

$n$개의 줄을 출력한다. $i$번째 줄에 $1$번 도시에서 $i$번 도시로 가는 $k$번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. $i$번 도시에서 $i$번 도시로 가는 최단경로는 $0$이지만, 일반적인 $k$번째 최단경로는 $0$이 아닐 수 있음에 유의한다. 또, $k$번째 최단경로가 존재하지 않으면 $-1$을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

---

문제 풀이

문제 이해

K번째 최단경로라는 것은 말 그대로 최단경로 탐색의 결과를 순서대로 나열했을 때, 가중치로 오름차순 정렬하여 K번째인 경로의 거리를 의미한다.

첫 번째 최단 경로를 찾는 문제는 간단하다. 1번의 다익스트라 알고리즘만 수행하면 되기 때문이다.

그럼 2번째는 어떤가? 이 문제를 해결하기 위해선 최단경로를 구성하는 에지 중 하나 씩을 없애보는 방법으로 접근해볼 수 있을 것 같았다.

그러나 정답을 만들기 위한 특정 간선을 찾는 것이 어렵고 연산횟수를 너무나 많이 증가시키기 때문에 다른 방식을 찾아야 했다.

접근방법 1 : 무식하게 접근하기

가장 단순하고 무식한 방법은 시작 노드에서 도착 노드로 모든 경로의 가중치들을 계산하고 정렬해보는 것이다.

이런 방식은 단언컨데 절대 유효한 시간안에 해결될 수 없다.

다만 가장 빠른 경로부터 순차적으로 방문이 가능하다면 굳이 모두 정렬시키지 않고도 순서를 추적해나갈 수 있다.

접근방법 2 : Priority Queue

우선순위 큐를 활용하여 다익스트라 알고리즘을 수행할 경우 간선 가중치 합을 기반으로 정렬하기 때문에 어떤 노드 B에 도달하는 경로가 큐에서 나올 경우, 이 순서는 가장 빠른 경로부터 오름차순 정렬한 순서를 따르게 된다.

따라서 단지 우선순위 큐에 지속적으로 간선을 집어 넣고 나온 횟수만 세어주면 정확히 몇 번째 최단경로인지를 바로 알 수 있다.

다행히 문제 조건상 $m \times k$가 300만보다 작거나 같기 때문에 유효한 시간 안에 종료가 될 것이다.

이때, k번을 넘겨 도달한 경우는 처리하지 않아야 하는데, 이 이유는 다음 상황을 고려해보면 알 수 있다.

C에 K번째로 도달하기 위해선 B에 K번 도달해야만 한다.

만약 그래프가 더 확장되어서 C에 도달하는 경로가 추가로 존재한다면, 결국 B, X 둘다 K번 방문 이전에 C로 가는 최단 경로가 우선순위 큐에 K번 이상 들어가게 될 것이기 때문에 결국 K번보다 많이 방문한 노드를 탐색대상에서 제외하면 된다.

---

구현

package kth_shortest_path;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String[] tokens = br.readLine().split(" ");
        int n = Integer.parseInt(tokens[0]), m = Integer.parseInt(tokens[1]), k = Integer.parseInt(tokens[2]);
        ArrayList<int[]>[] graph = new ArrayList[n+1];

        for(int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            tokens = br.readLine().split(" ");
            int a = Integer.parseInt(tokens[0]), b = Integer.parseInt(tokens[1]), c = Integer.parseInt(tokens[2]);
            graph[a].add(new int[] {b, c});
        }

        travel(graph, n, k);

    }

    public static void travel(ArrayList<int[]>[] graph, int n, int k) {
        int[] costs = new int[n+1];
        int[] visitCnt = new int[n+1];

        Arrays.fill(costs, -1);
        Arrays.fill(visitCnt, 0);

        PriorityQueue<int[]> pq = new PriorityQueue<>((i, j) -> i[1] - j[1]);
        pq.offer(new int[] {1, 0});

        while(!pq.isEmpty()) {
            int[] curVisit = pq.poll();
            if(visitCnt[curVisit[0]] >= k) continue;
            visitCnt[curVisit[0]]++;
            costs[curVisit[0]] = curVisit[1];

            for(int[] edge : graph[curVisit[0]]) {
                if (visitCnt[curVisit[0]] <= k) {
                    int nextCost = curVisit[1] + edge[1];
                    pq.offer(new int[] {edge[0], nextCost});
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; i++) {
            if(visitCnt[i] < k) sb.append(-1);
            else sb.append(costs[i]);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}

---

회고

최근 현대 오토에버라는 회사에 입사하게 되었다. 학교 선배나 인터넷에서 합격 수기, 합격 소식을 많이 접해본 기업이었고 대기업이기 때문에 선망하던 기업 중 하나였다.

채용 공고를 살펴보던 중 기술스택이 들어맞고 근무지도 서울이 아니라 지내기 편할 것 같아 덜컥 지방 근무지로 지원했다.

그러나, 실제로 내가 겪은 환경은 너무나 달랐다. 내가 원했던 대기업 사원의 삶과는 너무 거리가 멀었다.

근무지 주변에 지낼만한 곳도 없었고, 근무 시간도 공장 근무 사이클과 맞춰야 했기 때문에 굉장히 일찍 출근해야 했다.

무엇보다 지금껏 공부해온 서버, 인프라 개발과는 거리가 먼 직무이며 레거시 유지보수 업무만을 수행해야 했기 때문에 성장하기 어려운 환경으로 보였다.

물론 내 스펙을 고려해보면 감지덕지이고 높은 연봉을 쳐주는 직장이지만 출퇴근 피로도와는 별개로 성장할 수 없다는 점은 명확히 치명적인 약점으로 보였다.

일단, 이사를 해버렸고 당분간은 생활을 유지할 수 있어야 하기 때문에 직장에 다니기로 했다..

다만, 서버 개발자라는 꿈을 포기하고 싶지는 않다.. 그래서 1일 1문제를 목표로 다시 코딩을 시작해야겠다.

최근 마무리한 프로젝트들도 정리해서 포트폴리오로 만들고 성장할만한 회사를 찾는 것. 그것부터 차근차근 너무나 멀어져버린 나의 일상을 회복해야겠다.