[프로그래머스]level3-여행경로-Python[파이썬]

s2ul3·2022년 9월 26일
0

문제링크

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에 먼저 들어온 노드를 나중에 방문하게 만드려면 역순으로 노드를 정렬해야함.

profile
statistics & computer science

0개의 댓글