Programmers Lv.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"]

📖 문제 풀이

Code_1 - 실행 에러

from collections import deque
def solution(tickets):
    answer = []
    visited = [False]*len(tickets)
    q = deque()
    q.append("ICN")
    while q:
        airs = {}
        air = q.popleft()
        answer.append(air)
        for i in range(len(tickets)):
            if not visited[i] and tickets[i][0] == air:
                airs[tickets[i][1]] = i
        if len(airs) >= 1:
            airs = sorted(airs.items())[0]
            visited[airs[1]] = True
            q.append(airs[0])
    return answer

• 적용한 적이 없고 출발지가 같다는 조건하에 dictionary에 담아 알파벳 순서대로 정렬하도록 구현하였음
• bfs 알고리즘을 이용함

Code_2 - 성공

def solution(tickets):
    answer = []
    visited = [False]*len(tickets)
    tickets = sorted(tickets, key=lambda x: (x[0], x[1]))
    def dfs(air, path):
        if len(path) == len(tickets)+1:
            answer.append(path)
            return answer
        for idx, tick in enumerate(tickets):
            if not visited[idx] and air == tick[0]:
                visited[idx] = True
                dfs(tick[1], path+[tick[1]])
                visited[idx] = False
    dfs('ICN', ['ICN'])
    return answer[0]

• code_1에서와 같이 bfs를 이용해 해결하기 어려움을 겪어, dfs 알고리즘을 이용해 구현함
• 우선 ticket를 알파벳 순으로 정렬한 후 tickets의 수보다 공항 경로가 1만큼 많은 경우 반복문을 종료함