[프로그래머스 Lv.3] 여행경로

def solution(tickets):
    answer = []
    graph = {}
    
    for i in range(len(tickets)):
        if tickets[i][0] not in graph:
            graph[tickets[i][0]] = [tickets[i][1]]
        else:
            graph[tickets[i][0]].append(tickets[i][1])
            graph[tickets[i][0]].sort(reverse=True)
            
    print(graph)
    
    stack = ["ICN"]
    
    while stack:
        top = stack[-1]
        
        if top not in graph or not graph[top]:
            print("stack pop : ",stack[-1])
            answer.append(stack.pop())
        else:
            print("graph top pop : ",graph[top][-1])
            stack.append(graph[top].pop())
                
    return answer[::-1]

이번 문제는 주어진 항공권을 사용해서 여행경로를 짜되, 가능한 경로가 2개 이상인 경우에는 알파벳 순서대로 이동해야 하는 문제이다.

 

사전 자료형을 사용해서 각 공항에서 이동할 수 있는 경로를 리스트로 모두 저장하고 정렬하는 것까진 좋았는데, 단순히 알파벳 순만으로 이동하다보면 '경로가 끊기는 경우'와 '중복되는 경로가 있는 경우' 때문에 테스트케이스 1,2번이 틀리게 되었다.

 

2일동안 고민하고 풀다가 정 풀리지 않아 다른 사람의 풀이를 보았는데, 스택을 사용하여 생각보다 간단하게 풀 수 있었다.

 

1. 해당 공항에서 이동할 수 있는 공항이 없거나(top not in graph) 2. 더이상 이동할 수 있는 공항이 없는 경우(not graph[top]) 최종적인 경로이기 때문에 answer에 추가해주고, 아직 공항에서 이동할 수 있는 경로가 있는 경우에는 이동할 수 있는 경로를 넣어주는 방식으로 풀 수 있었다.

 

이렇게 스택으로 풀 수 있는 이유는 '모든 도시를 방문하는 경우는 반드시 존재한다'는 조건 덕분이다.

 

스택을 이용한 DFS를 다시 한번 상기시킬 수 있었던 문제였다 .. 갈길이 멀구나 ... ㅎㅎ