[프로그래머스/Python] 여행경로 (DFS)

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3

문제 풀이법을 떠올리는 데 정말 애를 먹었다.
dfs로 풀 수 있을 것 같은데, 선뜻 풀이방법이 생각이 나지 않아서 다른 게시물을 참고했다.출처

풀이방법

• 먼저 ticket을 그래프형태로 생성한다. (알파벳 순으로 sort까지 해주었다.)
• dfs를 구현하여 stack이 빌 때까지 모든 점을 순회한다
  스택에서 가장 위 데이터(출발지점이 "ICN"이니 여기부터) 가져온다
  • 가져온 데이터(top)가 그래프에 없거나 (top not in routes)
  • 티켓을 모두 사용한 경우 (len(route[top]) == 0 )
  • path에 저장한다 (path.append(stack.pop())
  • else -> routes[top].pop(0)을 stack에 append 한다. (경로가 존재하므로)

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]