https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3
문제 풀이법을 떠올리는 데 정말 애를 먹었다.
dfs로 풀 수 있을 것 같은데, 선뜻 풀이방법이 생각이 나지 않아서 다른 게시물을 참고했다.출처
from collections import defaultdict
def solution(tickets):
answer = []
def init_graph():
routes = defaultdict(list)
tickets.sort(key = lambda x:(x[1], x[0]))
for key, value in tickets:
routes[key].append(value)
return routes
def dfs(start):
stack = [start]
path = [] # 가려고 하는 경로를 저장하는 변수
while len(stack) > 0: # stack이 비어있을 때까지
top = stack[-1] # 스택의 맨 뒤가 top
print(stack)
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top].pop(0))
return path
routes = init_graph()
print(routes)
answer = dfs("ICN")
return answer[::-1]