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

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

프로그래머스

 

아이디어

처음에 bfs로 풀었다가 테케 1, 2 번을 통과하지 못했다. 문제에 아래와 같은 제시 부분이 있어서 알파벳 순서가 빠른 것 부터 탐색해서 일어난 일이었다. 

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

그래서 가능한 모든 경로를 탐색하고, 정렬한 뒤 return하도록 코드를 수정하였다. 

전체 코드

import copy

def solution(tickets):
    
    answer = []
    
    def dfs(depth, goal, departure, route, lefts):
        nonlocal answer
        
        if depth == goal:
            answer.append(route)
            return
        
        for idx, l in enumerate(lefts):
            if l[0] == departure:
                tmp_route = copy.deepcopy(route)
                tmp_lefts = copy.deepcopy(lefts)
                tmp_lefts.pop(idx)
                dfs(depth+1, goal, l[1], tmp_route+[l[1]], tmp_lefts)
                
    dfs(0, len(tickets),"ICN", ["ICN",], tickets)
    answer.sort()
    return answer[0]