[알고리즘] 프로그래머스 - 여행경로

프로그래머스 - 여행경로

파이썬 알고리즘 인터뷰와 리트코드의 일정 재구성과 동일한 문제이다. 하지만 풀이가 정확히 기억나지 않아 다소 비효율적으로 풀었다.

내 풀이

from collections import defaultdict

ans = []

def dfs(start, ticket_dict, path):
    global ans
    for value in ticket_dict.values():
        if value:
            break
    else:
        ans.append(path)

    if ticket_dict[start]:
        for i in range(len(ticket_dict[start])):
            next_dest = ticket_dict[start].pop(i)
            dfs(next_dest, ticket_dict, path+[next_dest])
            ticket_dict[start].insert(i, next_dest)

def solution(tickets):
    global ans
    ticket_dict = defaultdict(list)
    for ticket in tickets:
        ticket_dict[ticket[0]].append(ticket[1])

    for key, value in ticket_dict.items():
        ticket_dict[key].sort()

    dfs("ICN", ticket_dict, ["ICN"])
    return ans[0]

향상된 풀이

from collections import defaultdict

def solution(tickets):
    graph = defaultdict(list)
    for a, b in sorted(tickets):
        graph[a].append(b)

    route = []
    def dfs(a):
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)

    dfs("ICN")
    return route[::-1]

# print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]), ["ICN", "JFK", "HND", "IAD"])
# print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]), ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"])
# print(solution([["ICN", "JFK"]]))
print(solution([['ICN','B'],['B','ICN'],['ICN','A'],['A','D'],['D','A']]), ['ICN', 'B', 'ICN', 'A', 'D', 'A'])

애초에 딕셔너리에 넣을 때 sort 해서 넣으면 나중에 하나씩 정렬해줄 필요가 없다.

경로가 끊기는 경우가 없기 때문에 route에 모든 경로를 담을 수 있는 것이다.