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

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

dfs로 풀어야 겠다고 떠올렸다 

그런데 보통 입력이 숫자로 주어졌고, 나는 그래프를 표현할 때 주로 이차원 리스트를 사용했는데 

각각의 node에 해당하는 공항 이름들이 문자열이다보니, 처리를 쉽게 하기 위해서는 dictionary 자료형이 낫다고 생각했다. 

내가 좋아하는.. 쓰기 편한 defaultdict으로 초기화 없이 우선 정의해주고, 

for 문에서 각각 그래프와, visited 딕셔너리에 False값을 넣어 처리해주었다. 

from collections import defaultdict
def solution(tickets):
    answer = []
    n = len(tickets)
    graph = defaultdict(list)
    visited = defaultdict(list)
    for i in range(n):
        graph[tickets[i][0]].append(tickets[i][1])
        visited[tickets[i][0]].append(False)
    
    def dfs(start, path):
        if len(path) == n+1:
            answer.append(path)
            return 
        
        for i in range(len(graph[start])):
            if not visited[start][i]:
                visited[start][i] = True 
                dfs(graph[start][i],path+[graph[start][i]])
                visited[start][i] = False 
    
    
    dfs("ICN", ["ICN"])
    
    answer.sort()
    return answer[0]