Post

등산코스 정하기

2022 카카오 인턴십 코딩 테스트 기출 문제입니다.

Posted
By Kang Minjun
9 min read
등산코스 정하기

최근 Backend 코딩 테스트가 JAVA로만 응시가 가능한 시험이 많아 코드는 JAVA로 작성하였습니다.

문제링크

등산코스 정하기

아이디어

  1. 산봉우리 ↔ 출입구 사이의 경로들에서 edge의 가중치가 가장 낮은 경로를 구성하는 (산봉우리,출입구) 쌍을 찾아야합니다.

  2. 시작 출입구 → … → 산봉우리 → … → 시작 출입구를 구성하는 경로에서 다음과 같은 사실을 알 수 있습니다.

    • 산봉우리는 한 번만 방문할 수 있습니다. 산봉우리 부터 그래프 탐색을 진행하여, 탐색하려는 노드가 산봉우리일 경우 탐색을 진행하지 않는 식으로 탐색을 구성할 수 있습니다.
    • 출입구 → 산봉우리에 도달하는 경로와 동일한 경로로 산봉우리 → 시작 출입구로 이동하는 것이 최적해라는 것을 알 수 있습니다.
      • 산봉우리에 도달하기 까지 누적 간선의 가중치의 최솟값으로 탐색했다는 것이 보장되기 때문입니다.
      • 또한 양방향 간선이고 추가 제약이 없기 때문입니다.

  3. 시간 복잡도를 고려해봅시다.

    • N≤5×104 이고 경로의 개수≤2×105 입니다.

    • 산봉우리와 출입구의 수는 모두 N 개 이하입니다. 또한, 산봉우리이면서 출입구인 경우는 없으니 산봉우리의 수와 출입구의 수를 다음과 같이 표현할 수 있습니다.
      • 산봉우리의 수=N−출입구의 수−쉼터의 수
      • 출입구의 수=N−산봉우리의 수−쉼터의 수
    • 대략적으로 산봉우리의 수와 출입구의 수가 N2 일 때 연산의 횟수를 고려해보면 시간 제한에 걸릴 수도 있겠다는 생각을 하였습니다.
      • 산봉우리의 수 만큼 다익스트라를 돌리는 방식은 O(N2∗E×logN2) 의 시간이 걸립니다. E≈2×105 이고 N≤5×104 이므로 5∗109 번의 연산 이상을 요구하는 것을 알 수 있습니다.

  4. 불필요한 연산을 Pruning 해봅시다.

    • 다익스트라를 산봉우리의 수만큼 수행할때의 연산들이 중복되거나 불필요한 것이 없는 지 확인해봅시다.
    • 다음과 같은 상황에서 불필요한 연산이 수행됩니다.
      • 이전 summit에서 탐색을 완료했던 노드의 intensity 가 현재 summit의 탐색 도중 마주한 노드의 intensity 보다 작을 때 탐색을 진행하는 것은 불필요합니다. (이전 경로가 더 최적인 것이 자명)

소스코드

시간 초과를 받았던 코드 (아이디어 3번까지만을 구현)

입력으로 들어오는 모든 summits 들에 대해서 각각을 다익스트라 알고리즘을 활용하여 탐색하는 방식입니다.

아이디어 3번에서 기술하였듯, 특정 테스트케이스에서는 시간 초과를 받았습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

import java.util.*;
class Solution {
    boolean[] isGate, isSummit;
    List<int[]>[] adj;
    
    void init(int n, int[][] paths, int[] gates, int[] summits) {
        isGate = new boolean[n + 1];
        isSummit = new boolean[n + 1];        
        
        Arrays.sort(gates);
        Arrays.sort(summits);
        
        adj = new ArrayList[n + 1];
        for (int i = 1;  i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for (int[] path : paths) {
            int u = path[0], v = path[1], w = path[2];
            adj[u].add(new int[] {w, v});
            adj[v].add(new int[] {w, u});
        }
        
        for (int gate : gates) {
            isGate[gate] = true;
        }
        
        for (int summit : summits) {
            isSummit[summit] = true;
        }
        
    }
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        init(n, paths, gates, summits);
        int[] answer = new int[] {-1, 0x3f3f3f3f};

        // 산봉우리 -> 출입구까지의 거리
        for (int summit : summits) {
            // {현재까지의 intensity, current}
            int[] intensity = new int[50001];
            Arrays.fill(intensity, 0x3f3f3f3f);
            
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0], o2[0]));
            pq.add(new int[] {0, summit});
            intensity[summit] = 0;
            
            while (!pq.isEmpty()) {
                int[] polled = pq.poll();
                int acWeight = polled[0], current = polled[1];
                for (int[] edge : adj[current]) {
                    int weight = edge[0], next = edge[1];
                    if (isSummit[next] || intensity[next] <= Math.max(weight, acWeight)) {
                        continue;
                    }
                    intensity[next] = Math.max(weight, acWeight);
                    pq.add(new int[] {intensity[next], next});
                }
            }
            
            for (int gate : gates) {
                if (intensity[gate] < answer[1]) {
                    answer[0] = summit;
                    answer[1] = intensity[gate];
                }
            }
        }
        
        return answer;
    }
}

정답 코드(아이디어 4번까지 모두 구현)

한번에 모든 summit 들을 priority queue에 넣어서 탐색을 진행한다면, 4번에서 발견한 불필요한 탐색을 줄일 수 있습니다.

주의해야할 점은, 양방향 그래프에서의 사이클을 피하기 위해서 누적 intensity = intensity[next] 로 단순 비교해서는 안됩니다.

  • 누적 intensity = intensity[next] 라고 할지라도, 시작한 지점이 다르다면 사이클이 발생한 것이 아니며, 이 경우에도 경로 탐색을 진행해주어야 하기 때문입니다.
    • 경로 탐색을 진행하는 이유는 intensity가 동일할 때, 가장 번호가 빠른 summit의 번호를 가져와야하기 때문입니다.
    • 62 ~ 64 번 라인에서 해당 조건에 대한 분기문을 확인할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

import java.util.*;
class Solution {
    boolean[] isGate, isSummit;
    List<int[]>[] adj;
    
    void init(int n, int[][] paths, int[] gates, int[] summits) {
        isGate = new boolean[n + 1];
        isSummit = new boolean[n + 1];        
        
        Arrays.sort(gates);
        Arrays.sort(summits);
        
        adj = new ArrayList[n + 1];
        for (int i = 1;  i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        for (int[] path : paths) {
            int u = path[0], v = path[1], w = path[2];
            adj[u].add(new int[] {w, v});
            adj[v].add(new int[] {w, u});
        }
        
        for (int gate : gates) {
            isGate[gate] = true;
        }
        
        for (int summit : summits) {
            isSummit[summit] = true;
        }
        
    }
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        init(n, paths, gates, summits);
        int[] answer = new int[] {0x3f3f3f3f, 0x3f3f3f3f};

        int[] startPoint = new int[50001]; // intensity[k] 를 만드는 startPoint
        Arrays.fill(startPoint, 0x3f3f3f3f);
        int[] intensity = new int[50001];
        Arrays.fill(intensity, 0x3f3f3f3f);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[0], o2[0]));
        
        for (int summit : summits) {
            // {intensity 누적 결과, 시작점, 현재지점}
            startPoint[summit] = summit;
            intensity[summit] = 0;
            pq.add(new int[] {0, summit, summit});
        }
        
        while (!pq.isEmpty()) {
            int[] polled = pq.poll();
            int acWeight = polled[0], start = polled[1], current = polled[2];
            for (int[] edge : adj[current]) {
                int weight = edge[0], next = edge[1];
                
                if (isSummit[next] || intensity[next] < Math.max(weight, acWeight)) {
                    continue;
                }
                
                if (intensity[next] == Math.max(weight, acWeight) && startPoint[next] <= start) {
                    continue;
                }
                
                startPoint[next] = start;
                intensity[next] = Math.max(weight, acWeight);
                pq.add(new int[] {intensity[next], start, next});
            }
        }
        
        for (int gate : gates) {
            if (intensity[gate] < answer[1]) {
                answer[0] = startPoint[gate];
                answer[1] = intensity[gate];
            } else if (intensity[gate] == answer[1]) {
                answer[0] = Math.min(answer[0], startPoint[gate]);
            }
        }

        
        return answer;
    }
}
Problem Solving, Programmers
algorithm
This post is licensed under CC BY 4.0 by the author.