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

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

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

from collections import defaultdict, deque

def solution(tickets):
    answer = []
    neighbors=defaultdict(list)
    for start, end in tickets:
        neighbors[start].append(end)
    q=deque()
    q.append((["ICN"], 0, list(tickets)))
    while q:
        routes, cnt, temp_tickets=q.popleft()
        start=routes[-1]
        if (cnt==len(tickets)):             #다 돌았으면 answer 반환
            answer.append(routes)
        if neighbors.get(start) == None:    #start가 출발지인 항공권이 없는 경우
            continue
        for end in neighbors[start]:
            if [start, end] in temp_tickets: #쓰지 않은 ticket이 있을 경우
                temp_tickets.remove([start,end])
                q.append((routes+[end],cnt+1,list(temp_tickets)))
                temp_tickets.append([start,end])
    
    answer.sort()
    return answer[0]

엄청 헤매다.. 해답을 보았다. 자꾸 히든테케에서 걸렸다..

 

BFS 로 접근하는 방법을 취했다.

그리고 따로 visit 배열 만들어주지 않고 사용가능한 tickets 배열을 큐에 넣어 이를 체크하여 방문할 수 있도록 했다.

tickets의 길이만큼 방문했을 때, 그 routes를 answer에 넣어준다.

 

다른 분들의 코드를 보니 DFS로도 풀 수 있다.

쭉 DFS로 파고들어가다가 routes 의 길이가 N+1가 나오면 해당 route를 리턴하는 식이다. 이 경우에는 사전에 오름차순 정렬이 필요하다.