여행경로: DFD풀이

문제 설명

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

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

 

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

 

from collections import defaultdict

def solution(tickets):
    answer=[]
    route = defaultdict(list)

    for ticket in tickets :
        route[ticket[0]].append(ticket[1])
    
    for key in route.keys():
        route[key].sort(reverse=True)

    stack = ["ICN"]
    while stack:
        tmp = stack[-1]
        if route[tmp] == []:
            answer.append(stack.pop())
        else:
            stack.append(route[tmp].pop())
    answer.reverse()
    return answer

 

문제 핵심

버벅거린 이유

1) 파이썬 문법에 대한 무지: 내용보단, 언어 자체를 이해하지 못해서 오래걸렸다.

2) 문제에서 정의한 유니버스를 제대로 인식하지 못했다. 

조건은 여러가지 였지만, 문제의 핵심이 되는 조건은 주어진 항공권 모두 이용 이다.

이는 생각할 수 있는 모든 경우의 수를 급격히 줄여준다.

 

모든 티켓을 다 쓴다는 말은

입력 데이터가 조건에 맞게 나온다면,  주어진 항공권을 모두 이용하여 릴레이 여행이 가능하단 말이다.

즉, 도착지는 다음의 출발지가 되고,  처음 노드로만으로도 모든 노드를 방문할 수 있다는 말과 같다.

 

세부 사항으로써 A to B 항공권을 다음과 같이 Dictionary 형태로 바꿔놨을 때

 

ICN : ["B"]

B: ["C"]

C: ["E", "ICN"]

D: ["C"]

E: ["D"]

 

 

ICN(팝7) → B(팝6) → C(팝5) → ICN'(팝1)                           

                                                         → E(팝4) → D(팝3) → C(팝2)

 

REVERSE하기 전:  ICN' → C → D → E → C → B → ICN

정답: ICN → B → C → E → D → C → ICN'

 

논리: 모든 노드들은 연결되어 형태를 가져야만 하므로, 더이상 방문할 수 없는 노드는 가장 마지막 방문지가 될 것이며

이를 n-1 시키면 n은 결국 출발지가 될 것이다.