❓문제 설명
- 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "
ICN" 공항에서 출발합니다.
- 항공권 정보가 담긴 2차원 배열
tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
❗제한 조건
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는
3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가
2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
📌 풀이
- 모든 간선을 거쳐 경로를 구하는 문제 이므로 깊이 우선 탐색(DFS)을 응용하여 풀 수 있을 것 같다.
- 모든 정점 방문이 아니라 모든 간선을 거쳐야 하는 문제이기에 간선을 거치는 순서를 결정하는 문제이다.
- 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우 알파벳 순서를 따르도록 조건을 처리한다.
- 스택을 이용하여 재귀적인 "한 붓 그리기" 문제를 해결하면 된다. (DFS 알고리즘의 응용)
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:
top = stack[-1]
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top][-1])
routes[top] = routes[top][:-1]
return path[::-1]
