# tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] -> ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
# ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만
# ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞서기 때문에 이 경로를 return
## 의사 코드 ##
# 주어진 항공권을 모두 이용 -> DFS
# stack
# tickets를 딕셔너리 그래프 형태로 만들기
# defaultdict(list)
# 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
# -> DFS 수행할 때 노드 중 알파벳 순서가 더 앞에 있는 것을 방문
# for k in graph.keys():
# graph[k].sort(reverse=True)
# -> stack 구조를 사용할 것이기 때문에 역순으로 정렬해야 알파벳 순서로 꺼내짐
통과한 코드
from collections import defaultdict
def solution(tickets):
answer = []
# 그래프에 정보 입력
graph = defaultdict(list)
for start, arrive in tickets:
graph[start].append(arrive) # 방향 그래프니까 한 번만 append
# 알파벳 순으로 정렬
for k in graph.keys():
graph[k].sort(reverse=True) # stack 구조를 사용할 것이기 때문에 역순으로 정렬
q = ["ICN"] # stack
while q:
city = q[-1] # => q.pop()할 값
if city not in graph or len(graph[city]) == 0:
answer.append(q.pop())
else:
q.append(graph[city][-1])
graph[city] = graph[city][:-1]
# answer 역순 정렬
answer.reverse()
return answer
-> tickets의 정보를 graph라는 dict로 생성, stack을 활용한 DFS
stack 구조를 사용하기 때문에 graph의 values를 정렬할 때 역순으로 정렬하는 것에 주의
과정 확인
tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
"""
정렬 전 graph: defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})
정렬 후 graph: defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']})
시작 q: ['ICN']
city: ICN
graph[city][-1]: ATL
슬라이싱 전 graph[city]: ['SFO', 'ATL']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL']
남은 graph[city]: ['SFO']
city: ATL
graph[city][-1]: ICN
슬라이싱 전 graph[city]: ['SFO', 'ICN']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN']
남은 graph[city]: ['SFO']
city: ICN
graph[city][-1]: SFO
슬라이싱 전 graph[city]: ['SFO']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO']
남은 graph[city]: []
city: SFO
graph[city][-1]: ATL
슬라이싱 전 graph[city]: ['ATL']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL']
남은 graph[city]: []
city: ATL
graph[city][-1]: SFO
슬라이싱 전 graph[city]: ['SFO']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']
남은 graph[city]: []
city: SFO
city pop 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL']
city: ATL
city pop 후 q: ['ICN', 'ATL', 'ICN', 'SFO']
city: SFO
city pop 후 q: ['ICN', 'ATL', 'ICN']
city: ICN
city pop 후 q: ['ICN', 'ATL']
city: ATL
city pop 후 q: ['ICN']
city: ICN
city pop 후 q: []
역순 정렬 전 answer: ['SFO', 'ATL', 'SFO', 'ICN', 'ATL', 'ICN']
['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']
"""
다른 풀이
def solution(tickets):
answer = []
visited = [False]*len(tickets)
def dfs(airport, path):
if len(path) == len(tickets)+1:
answer.append(path)
return
for idx, ticket in enumerate(tickets):
if airport == ticket[0] and visited[idx] == False:
visited[idx] = True
dfs(ticket[1], path+[ticket[1]])
visited[idx] = False
dfs("ICN", ["ICN"])
answer.sort()
return answer[0]
