프로그래머스(programmers) 여행경로 python 정답[DFS 풀이]

프로그래머스(programmers) 여행경로 python 정답[DFS 풀이]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

문제 정답[BFS+STACK]

입출력 예

어디선가 복붙한 소스 코드를 첨부한다(BFS + STACK)

from collections import defaultdict
def solution(tickets):
    # 1. 그래프 생성
    routes = defaultdict(list)

    for (start, end) in tickets:
        routes[start] = routes[start] + [end]  

    # 2. 시작점 - [끝점] 역순으로 정렬
    # 스택 자료구조 형태로 pop 해서 사용하기 위함
    for r in routes.keys():
        routes[r].sort(reverse=True)

    # 3. DFS 알고리즘으로 path를 만들어줌.
    # 현재 방문할 공항을 스택에 유지
    st = ["ICN"]
    path = []
    
    while st:
        top = st[-1]
        # 더 이상 나갈 수 없는 경우
        if top not in routes or len(routes[top]) == 0:
            path.append(st.pop())
        else:
            # 현재 방문할 공항을 스택에 유지
            # 방문 여부 판단 대신, list 길이로 더 이상 해당 공항에서 이동할 수 없는지를 판단
            st.append(routes[top].pop())
    # 4. 만든 path를 거꾸로 돌림. 
    # 더 이상 갈 수 없는(마지막 종착지) 경우부터 스택에 쌓였기 때문
    answer = path[::-1]
    return answer

문제 해설 및 다른 해답

기존 DFS / BFS와 다르게 까다로운 점은,

그래프 순회는 DFS / BFS를 사용하지만, 추가적인 로직이 들어가 있다.

• 방문한 정점을 또 방문할 수 있다.
• 마지막으로 방문한 정점을 기억해야 한다.
• 정점 방문 순서를 기억해야 한다.
• 마지막으로 방문한 정점에서 출발한다.

후입선출 + stack 구조를 사용하므로 DFS가 가장 적절한 구조다.

DFS나 BFS 자체는 방문 순서를 중요하게 여기는 알고리즘은 아니기 때문에,

사실상 BFS와 스택 알고리즘이 동시에 조합된 문제라 여기는 것이 옳다.

(깊이 우선 순회 + 후입선출)

 

 

핵심 로직만 설명하면 다음과 같다

1. 그래프 탐색을 하면서, 현재 공항의 위치를 스택에 푸시한다.
2. 현재 공항에서 다음 공항으로 이동하면서, 항공권을 사용한다 (그래프 이동 가능 간선 목록에서 pop)
3. 현재 공항에서 더 이상 이동할 수 없으면 스택에서 팝해서 path에 푸시한다
4. path는 역순으로 푸시되었으므로 뒤집어준다.