프로그래머스 Level 3 여행경로

리스트가 아닌 딕셔너리로 그래프를 구현해서 풀어야되는 문제이다.

올바른 경로를 찾을 때까지 뺑뺑이를 돌려줘야 되는 문제라 dfs로 풀었다. 

핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의 value값을 삭제하고 재귀후에 다시 추가해주는 부분같다.

처음에 이 부분을 잘못 생각해서 푸는데 오래걸렸다... 

from collections import defaultdict

def dfs(N, graph, route, node):
    if len(route) == N+1:
        return route
    for i, n in enumerate(graph[node]):
        graph[node].pop(i)
        ret = dfs(N, graph, route+[n], n)
        graph[node].insert(i, n)
        if ret:
            return ret
        
def solution(tickets):
    N = len(tickets)
    graph = defaultdict(list)
    for s, e in tickets:
        graph[s].append(e)
    for k in graph:
        graph[k].sort()
    
    route = dfs(N, graph, ["ICN"], "ICN") 
    return route

 

추가로 defaultdict라는 친구에 대해 알게되었다.

여태까지 딕셔너리에 값을 채울 때나 키값이 있는지 조건문으로 확인할 때 get을 사용해서 따로 처리하곤

했었는데, defaultdict를 사용하면 오류 걱정없이 그냥 넣어주고 확인하면 된다!