프로그래머스 level3 여행 경로 (python)

Problem

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

Solution

from collections import defaultdict

def solution(tickets):
    def dfs(curr, remain):
        if len(remain) == 0:
            return [curr]
        
        next_tickets = [ticket for ticket in remain if ticket[0] == curr]
        
        if len(next_tickets) == 0:
            return 
        else:
            result = []
            for next_ticket in next_tickets:
                idx = remain.index(next_ticket)
                next_remain = remain[:idx] + remain[idx+1:]
                res = dfs(next_ticket[1], next_remain)
                if res is not None:
                    result.append([curr] + res)
                    
            return sorted(result)[0] if result else None 
        
    return dfs("ICN", tickets)

DFS를 이용하여 백 트래킹의 느낌으로 풀이하였다.