여행경로 (lv3)

문제 설명

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

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

제한사항

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

---

 본 문제에서는 어떤 그래프에 대해서 모든 "경로"를 방문할 수 있는 경우를 구해야한다. 다만 그 경로는 조건에 의해, 어떤 노드에서 다른 노드로 직접 가는 경로가 여러개 존재할 수 있고, 또한 노드의 방문 순서는 'ICN'에서 출발하되 사전순으로 우선순위가 결정된다는 것이다. 모든 경로를 다 방문할 수 있는 경우를 찾기전 까지는 탐색을 계속 진행하므로, 다시말해 처음으로 가능한 경로를 찾기만하면 탐색을 종료하면 되므로, DFS로 접근하는 편이 좋다.

 DFS를 방침으로 세웠다면, 이제 주어진 자료를 그래프로 나타낼 차례이다. 도시에서 도시로 이동하는 티켓을 하나의 노드로 볼 수도 있겠지만, 티켓은 중복될 수 있기 때문에 표현이 어렵고 또 그래프 생성에 O(N^2)의 시간복잡도가 소요될거라 판단했다. 대신 출발도시를 key값으로 하고 도착 도시가 들어있는 리스트를 value로 하는 딕셔너리로 그래프를 표현할 수 있는데, 마찬가지로 도착할 도시가 리스트내에 중복해서 존재할 수 있으며, 무엇보다 이렇게 표현할 경우 "도시에서 도시로 이동하는 티켓(경로)"에 대한 그래프가 아닌 노드를 key값인 각 도시로 보는 그래프가 만들어진다는 점을 유의해야 한다. 또한 노드이동 시 사전순으로 이동해야하니 인접노드를 삽입할 때 정렬된 형태로 넣을 수 있도록 한다. bisect 모듈의 insort_left를 이용했다.

중복된 티켓들이 주어진 경우에는 각 티켓을 하나의 노드로 보기가 힘들어진다.

따라서 각 도시를 노드로 보고, 대신 인접노드 리스트에 도시를 중복되게 넣는다.

 O(N) 만으로 그래프를 생성한것 까지는 좋지만, 여전히 문제 자체가 "모든 도시를 방문하는 경우"가 아닌 "모든 경로(티켓)을 방문하는 경우"를 요구하고 있으므로, DFS로 풀려고 해도 방문노드에 대한 처리가 까다롭다는 사실이 남아있다. 하지만 재귀함수를 이용할 경우 이 문제를 쉽게 해결할 수 있는데, 바로 어떤 노드에 방문할 때마다 인접 노드를 popleft 해서 재귀적으로 방문하고, 해당 재귀함수가 종료되면 popleft 했던 인접노드를 다시 인접노드 리스트 맨 뒤에 넣어줌으로써 인접노드 리스트 탐색이 모두 끝났을때도 기존의 순서를 유지시키는 것이다.

visited 리스트는, 위와 중복된 값이 들어올 수 있으므로 사용할 수 없다.

 예를 들어 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] 와 같은 티켓 리스트가 주어졌다고 하자. 도시에 대한 그래프는 다음과 같이 표현될 것이다.

 이때, 거듭 강조하지만 모든 경로를 방문하는 경우를 찾아야 하므로, 더이상 진행할 수 있는 경로가 없는 경우 재귀함수가 종료되며 popleft했던 인접노드를 다시 append 해줘야 한다. 맨 뒤에 넣어주는 이유는 순서를 유지하기 위함이다.

 

 재귀함수의 특징덕에, 위에서 구상한 방법을 손쉽게 직관적으로 구현할 수 있다. 재귀함수 내에서 for문이 돌며 노드를 순서대로 탐색해주기 때문에, 맨 끝까지 탐색을 진행하고 다시 돌아오는 지점을 따로 구현해줄 필요가 없다는 의미이다. 하지만 본 문제는 가장 처음 찾아낸 경우만을 답으로 요구하고 있는데, 재귀함수를 사용하면 원하는 경로를 찾아도 그래프를 전부 탐색할 때 까지 멈추지 않는다는 단점이 있다. 참고로 이 문제는 재귀함수를 사용하더라도 실행시간이 최대 120ms 정도로 통과 가능하다. 하지만 이번엔 반복문으로 dfs를 구현해줘서 원하는 지점에서 프로그램이 종료되게끔 해보았다.

 재귀함수가 아닌 반복문으로 DFS를 구현할 때, 가장 신경써줘야하는 부분은 바로 특정 노드에서 더 이상 진행할 수 없을 때 필요한 만큼 다시 되돌아 가는 것이다. 이 문제에서는, 만약 방문하고 있는 노드에 더 이상 방문할 수 있는 인접노드가 남아있지 않다면 그동한 방문했던 경로들을 다시 원래 그래프에 채워주는 방식으로 구현될 수 있다. 또 하나 주의할 것은, 재귀 함수로 풀었을 때는 인접노드 리스트를 순회하는 for문에서 재귀 함수가 호출되면 호출된 재귀 함수부터 실행되어 바로 인접노드를 popleft 해줄 수 있었지만, 반복문으로 풀 때는 인접노드를 순회하며 일단 스택에 담아만 놓고만 있다가, 실제로 해당 노드를 방문 했을때만 popleft 해줘야한다는 차이점이 있다.

코드

from bisect import insort_left
from collections import deque

def solution(tickets):
    
    graph = {}
    for dep,arv in tickets:
        if graph.get(dep):
            insort_left(graph[dep],arv)
        else:
            graph[dep] = deque([arv])
    length = len(tickets)
    stack = [('ICN',graph['ICN'][i]) for i in range(len(graph['ICN'])-1,-1,-1)]
    answer = ['ICN']
    while stack:
        prev,now = stack.pop()
        answer.append(now)
        graph[prev].popleft()
        if len(answer) == length+1:
            return answer
        if graph.get(now):
            for i in range(len(graph[now])-1,-1,-1):
                stack.append((now,graph[now][i]))
        else:
            while stack[-1][0] != answer[-1]:
                last = answer.pop()
                graph[answer[-1]].append(last)