https://school.programmers.co.kr/learn/courses/30/lessons/43164
스택을 이용하여 재귀적인 '한붓그리기' 문제를 해결 --> DFS 알고리즘 응용
#프로그래머스 풀이
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
# t[0] : 출발지점, t[1] : 도착지점
# routes에 출발지점 t[0]이 존재하는경우 이것의 value 리스트에 t[1]을 추가해준다. (리스트 덧셈을 이용하여)
# routes에 출발지점 t[0]이 존재하지 않은 경우 []를 생성하고 t[1]을 추가해준다. (리스트 덧셈을 이용하여)
for r in routes:
routes[r].sort(reverse = True) # 역순으로 정렬하는 이유 : 리스트의 끝 값을 불러오는 것이 더 쉬우므로
stack = ['ICN'] # 시작점
path = []
while len(stack) > 0:
top = stack[-1]
#top이 경로에 존재하지 않거나 top에서 갈 수 있는 곳이 없다면 --> stack에서 가장 끝값 즉 top을 빼내고 이 top을 path에 추가한다. (이곳은 마지막에 방문하게 된다.)
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top][-1]) # 앞에서 value를 역순으로 정렬했으므로 알파벳순으로 불러오려면 value의 끝에 값을 가져와야함.
routes[top].pop()
return path[::-1] # path에 먼저 들어온 노드를 나중에 방문하게 만드려면 역순으로 노드를 정렬해야함.