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

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

코드 바로보기

---

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

---

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

---

입출력 예

 

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

---

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

---

코드

using System;
using System.Collections.Generic;

public class Solution {
    
    string result;
    bool[] visit;
    
    void dfs(string[,] tickets, string cur, string path, int len)
    {
        //티켓 갯수랑 len길이랑 같으면 끝
        if(len==tickets.GetLength(0))
        {
            result = path;
            return;
        }
        
        for(int i=0; i<tickets.GetLength(0); i++)
        {
            //방문하지 않은 상태이면서 티겟이 다음 티켓이랑 같으면 항공권이 있다는 의미
            if(!visit[i] && tickets[i,0].Equals(cur))
            {
                //이어서 dfs
                visit[i] = true;
                dfs(tickets, tickets[i,1], path + tickets[i,1], len+1);
                visit[i]=false;
            }
        }
    }
    
    public string[] solution(string[,] tickets) {
        
        visit = new bool[tickets.GetLength(0)];
        List<string> list = new List<string>();
        
        //알파벳 순서 대로 정렬
        for(int i=0; i<tickets.GetLength(0)-1; i++)
        {
            for(int j=i+1; j<tickets.GetLength(0); j++)
            {
                //문자형으로 비교하면 오류
                //string.Compare로 진행
                if(string.Compare(tickets[i,1], tickets[j,1])==-1)
                {
                    string[][] tmp = new string[][] 
                    {
                        new string [] {tickets[i,0], tickets[i,1]}
                    };
                    tickets[i,0] = tickets[j,0];
                    tickets[i,1] = tickets[j,1];
                    tickets[j,0] = tmp[0][0];
                    tickets[j,1] = tmp[0][1];
                }
            }
        }
        
        //dfs 함수
        dfs(tickets, "ICN", "ICN", 0);
        
        //모든 공항이 3글자 이므로 3글자씩 끊어서 리스트 추가
        for(int i=0; i<result.Length; i+=3)
        {
            list.Add(result.Substring(i,3));
        }
        //리스트 배열화 하고 리턴
        string[] answer = list.ToArray();
        return answer;
    }
}