[Programmers 여행경로 : DFS/BFS, Python] - 스택 수열

2021, Oct 18    


프로그래머스 LvL 3 : 여행경로



Solution


from collections import defaultdict
def solution(tickets):
    graph = defaultdict(list)      
    for start, end in tickets:    
        graph[start].append(end)            # 단일 방향
        graph[start].sort(reverse = True)    # 알파벳 오름차순으로 정렬
    
    stack = ['ICN']     # 항상 출발은 인천공항
    route = []
    print(graph)
    
    while stack:
        cur = stack[-1] 
        if cur in graph and graph[cur]:      # 해당 공항에서 출발하는 티켓이 남아있을 때
            stack.append(graph[cur].pop())   # 사용한 ticket 은 pop, 공항 자체를 pop 시키는 게 아니라는 점이 포인트
        else:
            route.append(stack.pop())       # 최종 도착지(이 공항에서 출발하는 티켓이 없음)
    
    route.reverse()     # 도착한 순서대로 route 에 append 되기 때문에 reverse 를 시켜야 출발 -> 도착 여행경로가 됨
    
    return route


풀이과정 및 느낀점


우선 이 문제는 연결된 공항을 우선적으로 다 지나야 하기 때문에 알고리즘 유형은 DFS 로 볼 수 있다.
stack 으로 풀었는데, 오히려 stack 으로 푸니 도착지부터 route 에 append 시켜줘야 해서 더 헷갈렸다. 차라리 일반적인 dfs 풀이처럼 재귀로 풀었으면 정지조건에서 append 시키도록 처리하면 되니 덜 까다로웠을 거 같다.
또 개인적으로 이 문제를 풀 때 신경써줘야 했던 건 방문한 공항이 아닌 그곳에서 사용한 티켓을 pop 시켜줘야 했던 부분이다.
공항 자체는 티켓으로 연결되어있기만 하면 재방문이 가능하기 때문에 방문했다고 해서 visited 처리하는 것처럼 없애버리면 안 된다.
도착지 -> 출발지 역순으로 route 에 추가되기 때문에 출력할 때는 reverse 시켜주는 것도 포인트이다.

# Programmers # Python # DFS/BFS # Algorithm