<Lv.3> 여행 경로 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/43164

📕 문제 설명

항상 ICN 공항에서 출발하는 비행편이 있다. 주어진 항공권을 모두 사용해 여행경로를 짤 때 방문하는 공항 경로를 배열에 담아 반환하기

(가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로를 반환할 것)

• Input
  항공권 정보 담긴 2차원 배열 tickets
• Output
  방문하는 공항 경로를 담은 배열

예제

풀이

중복 티켓이 가능하다는 조건이 없어서 처음에 당연히 없는줄 알고 풀었는데 ㅎ..
+) 도중에 마지막 티켓에 먼저 들리는 경우 딕셔너리로 접근하려면 에러가 나는데 이걸 고려안해서 한참 걸렸다..

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    int ticketCount;
    public string[] solution(string[,] tickets) {
        ticketCount = tickets.GetLength(0);
        Dictionary<string, List<string>> ticketDict = new Dictionary<string, List<string>>();
        // ticket Dictionary 초기화
        for (int i = 0; i < ticketCount; i++)
        {
            string departureTicket = tickets[i, 0];
            string arrivalTicket = tickets[i, 1];
            if (!ticketDict.TryGetValue(departureTicket, out List<string> ticketList))
            {
                ticketDict[departureTicket] = new List<string>();
            }
            ticketDict[departureTicket].Add(arrivalTicket);
        }
        // 정렬 (여러 답 있을 때 알파벳 앞에거 반환 위함) 
        foreach(string key in ticketDict.Keys)
        {
            ticketDict[key].Sort();
        }
        HashSet<string> visited = new HashSet<string>();
        return GetPath("ICN", visited, new List<string>() {}, ticketDict).ToArray();
    }
    
    private List<string> GetPath(string currTicket, HashSet<string> visited, List<string> currPath, Dictionary<string, List<string>> ticketDict)
    {
        currPath.Add(currTicket); // 현재 ticket 추가하기
        if (currPath.Count == ticketCount + 1) return currPath; // 정답 찾은 경우
        if (!ticketDict.TryGetValue(currTicket, out var value)) // 만약 아직 정답 아닌데 더이상 경로 없는 티켓 만나는 경우 처리 위함
        {
            currPath.RemoveAt(currPath.Count - 1);
            return currPath;
        }
        
        for (int i = 0; i < ticketDict[currTicket].Count; i++)
        {
            string arrivalTicket = ticketDict[currTicket][i];
            if (!visited.Contains(currTicket + arrivalTicket + i.ToString())) // i 붙이는건 중복티켓 있기 때문에 처리 위함
            {
                visited.Add(currTicket + arrivalTicket + i.ToString());
                if (GetPath(arrivalTicket, visited, currPath, ticketDict).Count == ticketCount + 1)
                {
                    return currPath;
                }
                visited.Remove(currTicket + arrivalTicket + i.ToString());
            }
        }
        
        currPath.RemoveAt(currPath.Count - 1);
        
        return currPath;
    }
}

결과