[Python3]프로그래머스_여행경로

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43164

접근법

list의 각 원소가 list의 형태로 이루어진 list가 중첩된 형태의 자료형이 주어졌다. 처음에는 출발지,도착지를 명확하게 사용하기 어려울 것 같아 버전2의 코드처럼 dict 형태로 (key:출발지,value:도착지)로 변환하여 저장하였다.
1. dict에서 현재 여행지(current)를 key로 하는 value들을 찾는다.
2. 찾은 모든 value들에 대하여 dict에서 value를 제외하여 dfs의 인자로 전달한다.
3. 종료조건: 더 이상 현재 여행지(current)를 key로 하는 value들이 존재하지 않거나 모든 항공권을 소모하였을 시( len(tickets)+1의 여행지가 정답에 답겼을 시)

• dict로 변환하지 않고 단순 for문을 통하여 각각의 항공권을 사용하였는지 알 수 있는 flag 집합만 재귀함수의 인자로 넘겨주어 모든 케이스를 위와 같은 방법으로 검사할 수 있다.

코드

버전 1.

answer = []
def solution(tickets):
    tickets.sort(key=lambda x:x[1])  
    v = [0] * len(tickets) 
    def dfs(l,v):
        global answer
        new_l = l[:]
        new_v = v[:]
        current = new_l[-1]
        for index,val in enumerate(tickets):
            i,j = val[0],val[1]
            if( not new_v[index] and i == current ):
                new_l.append(j)
                if( len(new_l) == len(tickets)+1 and not len(answer) ): 
                    answer = new_l[:]
                    return
                new_v[index] = 1
                dfs(new_l,new_v)
                new_l.pop(-1)
                new_v[index] = 0
    dfs(['ICN'],v)
    return answer

버전 2.

import copy
answer = []
def solution(tickets):
    global answer
    d = {}
    for ticket in tickets:
        key,val = ticket[0],ticket[1]
        if( key in d ):
            d[key].append(val)
        else:
            d[key] = []
            d[key].append(val)
    for val in d.values():
        val.sort()
    def dfs(current,cities,dic):
        global answer
        new_cities = cities[:]
        new_cities.append(current)
        if( len(new_cities) == len(tickets)+1 and not len(answer)  ):
            answer = new_cities
            return
        if( current in dic and len(dic[current]) ):
            for place in dic[current]:
                new_dic = copy.deepcopy(dic)
                new_dic[current].remove(place)
                dfs(place,new_cities,new_dic)
    dfs('ICN',[],d)
    return answer