8. 프로그래머스 - 여행경로

문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.  - 모든 공항은 알파벳 대문자 3글자로 이루어집니다.  - 주어진 공항 수는 3개 이상 10,000개 이하입니다.  - tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.  - 주어진 항공권은 모두 사용해야 합니다.  - 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.  - 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. Tickets : [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] return   : ["ICN", "JFK", "HND", "IAD"]

문제 해결  1. 티켓을 정렬, 같은 출발지를 가진 도착지를 이름순으로 정렬한다.  2. DFS로 검색을 시작. 검색한 티켓은 검색체크 활성화  3. 체크가 활성화된 티켓은 다시 검색하지 않음  4. 깊게 검색하다 모든 티켓을 사용하지 않았는데 더 갈곳이 없다면 검색체크를 비활성화 하면서 해당 검색 종료  5. 아직 검색할게 남은 지역까지 비활성화하면서 계속 뒤로 가다가 검색할게 남은 다른 지역 검색  6. 모든 지역을 검색했다면 종료

    Dictionary<string, List<Tuple<string, int>>> dicTic = new Dictionary<string, List<Tuple<string, int>>>();
    List<string> answer = new List<string>();
    bool[] isChecks;
    int ticketCount;

    public string[] solution(string[,] tickets)
    {
        ticketCount = tickets.Length / 2;
        isChecks = new bool[ticketCount];
        
        //세팅
        for (int i = 0; i < ticketCount; ++i)
        {
            if (dicTic.TryGetValue(tickets[i, 0], out List<Tuple<string, int>> item))
            {
                item.Add(new Tuple<string, int>(tickets[i, 1], i));
                item.Sort((item1, item2) => item1.Item1.CompareTo(item2.Item1));
            }
            else
            {
                dicTic.Add(tickets[i, 0], new List<Tuple<string, int>>() { new Tuple<string, int>(tickets[i, 1], i) });
            }
        }

        //검색 시작
        if (DFS("ICN", 0, ref tickets))
        {
            answer.Add("ICN");
        }

        //저장된거 역전한뒤 리턴
        answer.Reverse();
        return answer.ToArray();
    }

    public bool DFS(string name, int count, ref string[,] tickets)
    {
        // 티켓을 전부 사용했다면 종료
        if (count == ticketCount)
        {
            return true;
        }
        // 검색
        else if(dicTic.TryGetValue(name,out List<Tuple<string, int>> list))
        {
            bool isCheck = false;
            foreach (var item in list)
            {
                // 이미 함 갔던 곳이라면 패스
                if (isChecks[item.Item2])
                {
                    continue;
                }
                // 가지 않았던 곳만 쳌
                else
                {
                    isChecks[item.Item2] = true;
                    if (DFS(item.Item1, count + 1, ref tickets))
                    {
                        answer.Add(item.Item1);
                        isCheck = true;
                        break;
                    }
                    else
                    {
                        isChecks[item.Item2] = false;
                    }
                }
            }
            return isCheck;
        }
        return false;
    }

 

상당히 애먹었다. 티켓들을 정렬하고 DFS로 최대한 적게 빠른 길을 찾으려 했는데 꽤 많은 시행착오를 겪었다.

결국 완성한 코드도 그렇게 좋다고 말하기 애매한 완성도고... 

 

특히 1번 테스트케이스가 날 그렇게나 괴롭혔는데 알고보니 중복 티켓에 대한 처리에 관련된 문제였다.

 

그리고 버전 차이인지  Dictionary<string, List<(string, int)>>  요게 안된다.