문제
주어지는 항공권을 모두 이용하여 여행경로 짜기
출발점은 항상 “ICN”
주어지는 공항 수는 3개 이상 10,000개 이하
tickets의 각 행 [a, b]는 a공항에서 b 공항으로 가는 항공권
주어지는 항공권을 모두 사용해야함.
가능한 경로가 2개 이상일 경우 알파벳 순서
모든 도시를 방문할 수 없는 경우는 주어지지 않음
입출력 예시
| tickets | return |
|---|---|
| [[“ICN”, “JFK”], [“HND”, “IAD”], [“JFK”, “HND”]] | [“ICN”, “JFK”, “HND”, “IAD”] |
접근
일반적인 그래프의 DFS, BFS 문제는 모든 정점을 방문하는 것을 기준으로 한다.
이 문제는 조금 다르게 주어지는 모든 간선을 사용하는 것이 목적이다.
DFS를 이용하여 남은 간선을 계속 따라가는 식으로 구현하면 될 것같다.
하지만 여기서 문제는 단순히 DFS를 이용하면 더 이상 남은 간선이 없을 때 이전 정점으로 돌아오는 부분인데,
이 문제에서는 그 부분이 해당 간선이 없으면 불가능하다.
따라서 진행이 막히는 경로는 따로 저장을 해두고 나머지 경로를 모두 탐색한 후 마지막에 추가해주는 식으로 하면 해결할 수 있을 것 같다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes:
routes[r].sort(reverse=True)
stack = ["ICN"]
path = []
while len(stack) > 0:
now = stack[-1]
if now not in routes or len(routes[now]) == 0:
path.append(stack.pop())
else:
stack.append(routes[now][-1])
routes[now] = routes[now][:-1]
path.reverse()
return path