프로그래머스: 여행 경로

문제

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

 

문제 풀이

 처음에 생각할 때는 딕셔너리를 사용하지 않고, 각 경로를 방문해보고 알파벳 순에 따라 가장 앞의 값을 반환하려고 하였다. 하지만 주어진 티켓의 방문 경로에 따라, 딕셔너리를 활용하여 출발지에서 방문가능한 경로를 추가하는 방식을 사용하면 백트랙킹을 하지 않고 문제를 풀 수 있다.

 

{
    'ICN': ['ATL', 'SFO'], 
    'SFO': ['ATL'], 
    'ATL': ['ICN', 'SFO']
}

 

 예제 #2의 경우, 딕셔너리를 통해 도착지의 알파벳 순으로 정렬하면 위와 같이 정렬할 수 있다. 정렬된 상태의 딕셔너리는 `INC`를 시작하으로 딕셔너리의 value의 첫번째인 `ATL`부터 방문하면 `ICN - ATL - ICN - SFO - ATL - SFO` 순으로 방문할 수 있다.

 

코드

from collections import defaultdict, deque


def solution(tickets):
    stack, answer = ["ICN"], deque()

    paths = defaultdict(list)
    for departure, arrival in tickets:
        # 사전순으로 방문하기 위해, 추가할 때 정렬.
        paths[departure] = sorted(paths[departure] + [arrival])

    while stack:
        cur_loc = stack[-1]
        
        # 현재 출발지로 부터, 방문가능한 경로가 있는 경우.
        if cur_loc in paths and paths[cur_loc]:
            stack.append(paths[cur_loc][0])
            paths[cur_loc].pop(0)
            continue
            
        # 출발지로 부터 방문 가능한 경로가 없는 경우.
        answer.appendleft(stack.pop())

    return answer