[파이썬] 프로그래머스 : 여행경로 (Lv.3)

[파이썬] 프로그래머스 : 여행경로 (Lv.3)

프로그래머스

---

풀이

방향성 생각

• 목적지 -> 도착지점 티켓 수를 딕셔너리로 카운팅한다.
• 딕셔너리 정보를 바탕으로 백트래킹 해주기.
• 이동 가능한 지점이 있으면 티켓을 소모하고 DFS를 돌린다.
• 이동이 불가능하면 그 노드는 더이상 이동하지 않는다.
• 경로가 필요하니 DFS 인자에 마지막 지점을 넘겨줘서 티켓을 모두 사용하는 경우에 경로를 저장하기.

전체코드

'''
티켓 수 백트래킹
'''
from collections import defaultdict as dd

def solution(tickets):
    
    T = len(tickets)
    infos = dd(lambda :dd(int))
    for a,b in tickets:
        infos[a][b] += 1
    
    def dfs(path,T):
        nonlocal infos,paths
        
        # 현재 위치
        dep = path[-1]
        
        # 티켓 모두 소모했으면 경로 추가
        if T==0:
            paths.append(path)
            return
            
        # 티켓 정보
        for arv,t in infos[dep].items():
		        # 티켓 있으면 티켓 사용하고 DFS
            if t:
                infos[dep][arv] -= 1
                dfs(path+[arv],T-1)
                infos[dep][arv] += 1
    paths = []
    dfs(['ICN'],T)
    paths.sort()

    return paths[0]

코멘트

• 기본 DFS