<Hard> Reconstruct Itinerary (LeetCode : C#)

https://leetcode.com/problems/reconstruct-itinerary/

📕 문제 설명

tickets[i] = [from_i, to_i], 출발 및 도착 항공편 정보이 주어질 때 여정을 재구성해서 반환하기

출발은 JFK에서 하며 다양한 여정이 나온다면 알파벳 순으로 order 가장 낮은 여정 반환하기

• Input
  ticket 정보
• Output
  reconstruct한 여정 정보

예제

풀이

public class Solution {
    Dictionary<string, List<string>> adjList;
    List<string> itinerary;
    public IList<string> FindItinerary(IList<IList<string>> tickets) {
        adjList = new Dictionary<string, List<string>>();
        // 인접리스트 초기화
        foreach (var ticket in tickets) 
        {
            string departure = ticket[0];
            string arrival = ticket[1];
            if (!adjList.ContainsKey(departure)) adjList[departure] = new List<string>();
            adjList[departure].Add(arrival);
        }

        // 알파벳 순 정렬
        foreach (string airport in adjList.Keys) adjList[airport].Sort();

        itinerary = new List<string>();
        DFS("JFK");

        // 재귀로 해서 역순으로 담겨있기 때문에 reverse해서 반환
        itinerary.Reverse();

        return itinerary;
    }

    private void DFS(string airport) 
    {
        if (adjList.ContainsKey(airport))
        {
            while (adjList[airport].Count > 0) // 인접한 것들에 대해 DFS로 탐색 
            {
                string nextAirport = adjList[airport][0];
                adjList[airport].RemoveAt(0);
                DFS(nextAirport);
            }
        }

        itinerary.Add(airport);
    }
}

결과