[프로그래머스 C#] Lv.3 여행경로

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

모든 티켓을 사용하여 방문하는 공항의 경로를 구하는 문제

- 경로가 여러가지 나올 경우 알파벳 순서가 앞서는 경우를 구해야 함

 

- dict<출발항공, 도착항공리스트> 로 선언해 그래프로 표현

 -> 알파벳 순서가 앞서는 경우를 구하기 위해 도착항공 리스트를 미리 정렬하고 앞 서는 순서부터 탐색

  -> 탐색된 첫 번째 경로가 알파벳 순서가 앞서는 모든 티켓을 사용하는 경로가 됨

 

+ 참조 형식 유의.!

 

DFS 알고리즘

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

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

    public class Solution
    {
        public string[] solution(string[,] tickets)
        {
            string[] answer = null;
            var dict = new Dictionary<string, List<string>>(); // 그래프 <출발지, 도착지리스트>
            var keyList = new List<string>(); // 공항들의 이름을 담는 리스트

            // 그래프 세팅
            for (int i = 0; i < tickets.GetLength(0); i++)
            {
                if (dict.ContainsKey(tickets[i, 0]))
                    dict[tickets[i, 0]].Add(tickets[i, 1]);
                else
                {
                    keyList.Add(tickets[i, 0]);
                    dict.Add(tickets[i, 0], new List<string>() { tickets[i, 1] });
                }
            }

            // 알파벳 순으로 가장 앞서는 경로를 탐색하기 위해 미리 정렬
            foreach (string str in keyList)
                dict[str].Sort();

            var stringArray = new string[tickets.GetLength(0) + 1]; // 방문 공항의 순서
            stringArray[0] = "ICN"; // 시작 공항 위치
            DFS(1, stringArray[0], stringArray, dict, ref answer);

            return answer;
        }

        // 항공권을 전부 사용하는 사전 순으로 가장 빠른 경우를 answer에 넣는 메서드
        public void DFS(int currIndex, string startStr, string[] stringArray, Dictionary<string, List<string>> dict, ref string[] answer)
        {
            // 여행경로가 세팅된 경우 모든 탐색을 종료
            if (answer != null)
                return;

            // 항공권 티켓을 다 사용한 경우
            if (dict.Values.Select(x => x.Count).Sum() == 0)
            {
                answer = (string[])stringArray.Clone(); // 배열을 복사해서 세팅
                return;
            }

            // DFS 탐색 중단 조건
            if (dict.ContainsKey(startStr) == false || dict[startStr].Count == 0)
                return;

            var list = dict[startStr]; // 리스트 참조 (가독성)
            
            // 갈 수 있는 공항에 대해 DFS 탐색 (알파벳이 앞서는순으로 탐색)
            for (int i = 0; i < list.Count; i++)
            {
                string endStr = list[i];
                stringArray[currIndex] = endStr;
                
                list.RemoveAt(i);
                DFS(currIndex + 1, endStr, stringArray, dict, ref answer);
                list.Insert(i, endStr);
            }
        }
    }