[프로그래머스, 파이썬] 여행경로 - 레벨 3 | 깊이/너비 우선 탐색(DFS/BFS)

📌 프로그래머스 Level 3 : 여행경로

회사에서 한 달간 장기 해외 출장을 갔다왔더니 알고리즘 풀이 연습을 계속 못하고 있었다.

📝 내 풀이

from collections import defaultdict
def solution(tickets):
    answer = []
    t_list = defaultdict(list)
    # t_list
    for i in range(len(tickets)):
        s = tickets[i][0]
        t = tickets[i][1]
        t_list[s].append((t,i))
        t_list[s].sort()
        
    visit = set([])
    def dfs(start,t_list,path,visit):
        nonlocal answer
        if answer != []:
            return answer
        if len(path) == len(tickets)+1:
            # 경로 모두 포함했으면 answer에 넣기
            answer = path
            return answer
        
        for arr_num in t_list[start]:
            arr = arr_num[0]
            n = arr_num[1]
            if (start,arr,n) not in visit:
                visit.add((start,arr,n))
                dfs(arr,t_list,path+[arr],visit)
                visit.remove((start,arr,n))
    
    dfs('ICN',t_list,['ICN'],visit)
    return answer

추가 TestCase

+TC 1

tickets :
[["ICN", "AAA"], ["ICN", "AAA"], ["ICN", "AAA"], ["AAA", "ICN"], ["AAA", "ICN"]]

return :
["ICN", "AAA", "ICN", "AAA", "ICN", "AAA"]

+TC 2

tickets :
[["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"]]

return :
["ICN", "A", "C", "A", "B", "D"]

📝 내 풀이2 (Old)

from collections import defaultdict
answer = []

def dfs(start,cnt,visit,graph,ticket,path):
    if cnt >= ticket:
        answer.append(path)
        return

    for i in range(len(graph[start])):
        if visit[start][i] == 0:
            visit[start][i] = 1
            dfs(graph[start][i],cnt+1,visit,graph,ticket,path+[graph[start][i]])
            visit[start][i] = 0

def solution(tickets):
    visit = defaultdict(list)
    graph = defaultdict(list)

    for start, end in tickets:
        visit[start].append(0)
        graph[start].append(end)
        graph[start].sort()

    answer.append("ICN")

    dfs("ICN",0,visit,graph,len(tickets),answer)

    return answer[1]

신기하게 한 달동안이나 알고리즘 문제를 안풀었는데, 다시 풀었더니 훨씬 더 빠르게 테스트케이스를 통과할 수 있었다.

답안1은 먼저 알파벳 순서대로 sort 후에 가능한 여행경로 1개만 구하고 끝낼 수 있고,

답안2(Old)는 모든 경로를 탐색 후 알파벳 순서가 빠른 경로를 선택하기 때문에 차이가 많이 나는 것 같다.