(C#) 등산코스 정하기

https://school.programmers.co.kr/learn/courses/30/lessons/118669?language=csharp

프로그래머스

 

 아우... 다익스트라를 변형해서 풀 수 있었다.

 

 문제에서 뭐 복잡하게 설명을 했지만, 굳이 등산로를 왕복할 필요는 없고 gate에서 summit으로 가는 임의의 경로들 중에서 intensity가 최소인 경로를 찾으면 된다.

 

 일반적인 다익스트라 알고리즘은 출발지에서 다른 정점들까지의 최소 비용을 구할 수 있다. 이 문제에서는 출발지에서 다른 정점들까지의 최소 비용을 구하는 대신 최소 intensity를 구해주면 된다.

 

 게다가 각 게이트를 출발지로 해서 따로따로 최소 intensity를 구할 것도 없이 모든 게이트를 다 때려박고 한꺼번에 구해도 된다. 왜냐면 어떤 게이트에서 출발했는지는 전혀 중요하지 않기 때문이다. 어떤 게이트에서 출발했던간에 정상에 도착했을때의 intensity만 최소로 만들면 된다.

 

 문제를 풀면서 헷갈렸던건 우선순위 큐를 구현하는 문제였다.

 C#에는 내장된 우선순위 큐가 없기 때문에(.NET 7버전 이상에서는 PriorityQueue가 제공된다. 하지만 테스트 환경은 이보다 버전이 낮은 것으로 보인다) 우선순위 큐를 직접 구현하거나 비슷한 자료구조를 사용해야한다.

 

 나는 SortedSet을 사용하기로 했다.

 

 SortedSet은 내부적으로 heap으로 구현됐기 때문에 우선순위 큐의 역할을 잘 수행할 수 있었다. 문제는 Set이기 때문에 같은 우선순위를 가지는 값을 중복으로 처리해서 받아들이지 못한다는 점이었다.

 나는 SortedSet에 넣어줄 요소를 int[2] 형태로 만들고, 커스텀 비교 연산자를 넣어주었다. int[2] element는 { intensity, idx }의 형태로 했다. 그리고 커스텀 연산자를 통해 만약 intensity가 다르다면 intesity를 기준으로 오름차순, intensity가 같다면 idx를 기준으로 오름차순 정렬하도록 했다.

 

 SortedSet<int[]> queue를 생성해주고, queue에 게이트를 모두 때려넣는다.

 그리고 다익스트라 알고리즘을 돌린다.

 

 queue에서 intensity가 최소인 정점을 꺼내고 current라고 한다.

 만약 current 가진 최소 intensity보다 현재 intensity가 더 크다면 그대로 패스한다.

 

 만약 current가 summit이라면 answer를 비교하고 갱신한다. 인접 노드를 살피지 않고 그대로 continue한다.

 

 current와 인접한 모든 노드들을 체크한다. 새로운 intensity는 지금까지의 intensity와 다음 노드까지의 비용 중 더 큰 값이 된다. 만약 새로운 intensity가 다음 노드의 기존 intensity보다 작다면 경로를 갱신한다. 최소 intensity 경로가 바뀌었으므로 queue에 넣는다.

 

 최종적으로 answer에 저장된 값을 반환하면 된다.

 

코드

using System;
using System.Collections.Generic;

public class Solution {
    public int[] solution(int n, int[,] paths, int[] gates, int[] summits)
    {
        // 가능한 제일 큰 값으로 초기화
        int[] answer = new int[] { 0, 10000001 };
        // 정점이 정상인지 체크
        bool[] isSummit = new bool[n + 1];
        for (int i = 0; i < summits.Length; i++)
        {
            isSummit[summits[i]] = true;
        }
        // 정점이 가진 최소 intensity를 저장
        int[] max_intensity = new int[n + 1];
        Array.Fill(max_intensity, -1);

        // 노드 구조체 생성
        Node[] nodes = new Node[n + 1];
        for (int i = 0; i < n + 1; i++)
        {
            nodes[i] = new Node(i);
        }

        // 인접 리스트 생성
        for (int i = 0; i < paths.GetLength(0); i++)
        {
            int u = paths[i, 0];
            int v = paths[i, 1];
            int w = paths[i, 2];
            nodes[u].adjacent.Add(new int[] { v, w });
            nodes[v].adjacent.Add(new int[] { u, w });
        }

        // SortedSet을 이용해서 우선순위 큐 구현
        SortedSet<int[]> queue = new SortedSet<int[]>(Comparer<int[]>.Create((lhs, rhs) =>
        {
            if (lhs[0].CompareTo(rhs[0]) == 0)
                return lhs[1].CompareTo(rhs[1]);
            return lhs[0].CompareTo(rhs[0]);
        }));

        // 모든 게이트를 때려박는다
        for (int i = 0; i < gates.Length; i++)
        {
            queue.Add(new int[] { 0, gates[i] });
            max_intensity[gates[i]] = 0;
        }

        // 다익스트라 알고리즘
        while (queue.Count > 0)
        {
            int[] current = queue.Min;
            queue.Remove(current);

            // 이전 노드가 계산한 intensity
            int current_intensity = current[0];
            int current_idx = current[1];

            // 이미 그보다 더 낮은 값으로 갱신되었다면 패스한다
            if (max_intensity[current_idx] != -1 && current_intensity > max_intensity[current_idx]) continue;

            // 현재 노드가 정상이라면 answer를 비교하고 갱신한다
            if (isSummit[current_idx])
            {
                if (current_intensity < answer[1])
                {
                    answer[0] = current_idx;
                    answer[1] = current_intensity;
                }
                else if (current_intensity == answer[1])
                {
                    if (current_idx < answer[0])
                    {
                        answer[0] = current_idx;
                    }
                }
                continue;
            }

            // 현재 노드에 인접한 모든 노드에 대해서 새로운 intensity를 계산한다
            Node current_node = nodes[current_idx];
            for (int i = 0; i < current_node.adjacent.Count; i++)
            {
                int[] next = current_node.adjacent[i];
                int next_idx = next[0];
                int next_cost = next[1];
                // 현재까지의 intensity와 다음 노드까지의 비용 중 큰 값
                int next_intensity = Math.Max(next_cost, current_intensity);

                // 다음 노드를 아직 방문하지 않았거나 새로운 intensity가 기존 intensity보다 작다면 갱신하고 queue에 넣는다
                if (max_intensity[next_idx] == -1 || next_intensity < max_intensity[next_idx])
                {
                    max_intensity[next_idx] = next_intensity;
                    queue.Add(new int[] { next_intensity, next_idx });
                }
            }
        }

        return answer;
    }

    struct Node
    {
        public int idx;
        public List<int[]> adjacent;

        public Node(int idx)
        {
            this.idx = idx;
            this.adjacent = new List<int[]>();
        }
    }
}

 

후기

 문제를 보자마자 다익스트라 알고리즘을 변형해야겠다는 생각은 들었다. 하지만 첫 구현에서는 모든 게이트를 한꺼번에 굴릴 생각을 못하고 따로따로 다익스트라 알고리즘을 수행했다. 그래서 뒤쪽 문제들에서 시간초과가 여럿 발생했다.

 그리고 처음에는 인접 리스트 대신 인접 행렬로 paths를 저장했는데, 이것 때문에 런타임 에러가 발생했다. 자세한 에러 내용은 표시되지 않았지만 아마 스택 오버플로우가 아니었을까?

 

 그 다음 문제는 우선순위 큐를 구현하는 것이었다. 처음에는 단순히 Queue를 그대로 사용했다. 그러나 다익스트라 알고리즘에서 우선순위 큐는 필수였다. Queue를 사용해서는 최소 비용을 구할 수 없다. 몇몇 케이스에서 실패가 떴다.

 다음은 List를 사용해서 수동으로 최소값을 구하는 것이었다. 당연히 시간초과가 발생했다.

 다음은 SortedSet을 사용하는 것이었다. 그러나 SortedSet을 사용하는데 있어 익숙하지 않아 대체 어떤 형태의 데이터셋을 넣어주어야 하나 고민했다.

 최종 코드에서는 각 노드가 가지는 최소 intensity 값과 이전 노드에서 계산한 intensity 값을 분리해서 사용하고 있지만 처음 구현에서는 두 값을 구분하지 않았다. 당연히 서로다른 두 값을 가지고 하나만 쓰려고 하니 로직이 제대로 작동할리가 없었다. 결국 혼자 힘으로 풀지 못하고 검색을 통해 아이디어를 얻었다.

 평범한 다익스트라 알고리즘이라면 몇번 구현해봤기 때문에 익숙하게 구현했겠지만, 변형해서 사용하려고 하니 머리가 너무 아팠다.