초이의 끄적끄적

프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)

# 여행경로 (Level 3)

• Point . dic로 그래프 만들고 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"] # 첫시작은 ICN
        path = []  # 가려고하는 경로를 저장하는 변수
        while stack:  # 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