[프로그래머스] 여행경로 파이썬(DFS)

 

from collections import defaultdict
def solution(tickets):
    # 특정 티켓의 인접 리스트를 구하는 함수
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    # 스택을 사용한 DFS
    def dfs():
        stack = ["ICN"]
        path = []  # 가려고하는 경로를 저장하는 변수
        while len(stack) > 0:  # stack이 비어있을 때까지
            top = stack[-1]
            # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))
        return path[::-1]

    routes = init_graph()
    for r in routes:
        routes[r].sort()

    answer = dfs()
    return answer

 

• { 시작점 : [도착점], ... } 형태의 인접 리스트 그래프를 생성합니다.
• ‘도착점’의 리스트를 정렬합니다. (알파벳 순서로)
• DFS 알고리즘을 사용해 모든 점을 순회합니다. (스택이 빌때까지)
  • 스택에서 가장 위 데이터(top)를 가져옵니다.
  • 가져온 데이터(top)가 그래프에 없거나, 티켓을 모두 사용한 경우, path에 저장
  • 아니라면, 가져온 데이터(top)을 시작점으로 하는 도착점 데이터 중 가장 앞 데이터(알파벳순으로 선택해야하므로)를 가져와 stack에 저장

 

출처: wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/