[프로그래머스] <여행경로> 파이썬

programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

시작점 인천인지 모르고 그냥 dfs 조지다가 머리 빠질 뻔함

 

def solution(tickets):
    tickets.sort(key = lambda x : (x[0], x[1]))
    route = ["ICN"]
    stack = []
    used = [False] * len(tickets)



    def dfs(i,ticket) :
        stack.append((i, ticket))
        route.append(ticket[1])
        used[i]= True
        flags = [False] * len(tickets)

        while False in used :
            for ind, tick in enumerate(tickets) :
                if route[-1] == tick[0] and not used[ind] and not flags[ind]:
                    dfs(ind,tick)
                    used[ind]= True
                    break
            else :
                route.pop()
                v, tick = stack.pop()
                flags[v] = True
                used[v] = False

    for ind, tick in enumerate(tickets) :
        if route[-1] == tick[0] and not used[ind]:            
            dfs(ind,tick)            
            break  
    return route

정확성 테스트

테스트 1 〉	통과 (0.10ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0