프로그래머스
- 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"] |
접근 방식
- 시작은 인천공항. 방문하는 공항을 스택에 집어 넣는다.-> ICN을 넣는다.
- 인천공항에서 갈 수 있는 공항은 AAA와 BBB가 있는데, AAA가 알파벳 순서가 우선하므로 AAA를 스택에 집어 넣는다.
- AAA를 넣었는데 갈 수 있는 곳이 없네 ? AAA를 꺼내서 어딘가에 적어둔다.
- 원래 공항인 인천공항에 돌아와서 나머지 DFS를 한다.
코드
def solution(tickets):
graph = dict()
for s, e in tickets:
if s in graph:
graph[s].append(e)
graph[s].sort(reverse=True) # 알파벳 빠른 순으로 빼내야하는데 stack은 후입선출이므로
else:
graph[s] = [e]
path = ['ICN']
ans = []
while path:
top = path[-1]
if top not in graph or len(graph[top]) == 0:
ans.append(path.pop())
else:
path.append(graph[top].pop())
ans.reverse()
return ans
