[프로그래머스 / Python] 여행경로

문제 링크: programmers.co.kr/learn/courses/30/lessons/43164

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

 

 

문제 설명

DFS를 이용해 모든 티켓을 사용하는 경로를 탐색합니다. 이때 DFS의 순서를 스택에 저장했다가 스택 top에서 갈 수 있는 경로가 없을 경우에 answer에 추가합니다. 갈 수 있는 경로가 없다는 것은 그 공항이 제일 마지막 방문지라는 의미입니다. 즉, answer에는 공항을 방문하는 순서가 거꾸로 저장되게 됩니다. 따라서 마지막에 answer을 뒤집어서 반환하면 됩니다. 

 

1. 티켓의 정보(start, end)를 딕셔너리 routes에 저장
2. routes는 start를 key로 하고, end를 리스트의 원소로 갖는 딕셔너리
3. DFS에서 pop을 이용해서 알파벳 순서대로 티켓을 사용하기 위해 각 key에 대해 value 리스트를 알파벳 역순으로 정렬
4. 스택에 출발 지점 "ICN"을 삽입
5. 스택 top을 start로 하는 티켓이 남아있지 않은 경우 top을 스택에서 꺼내서 answer에 삽입
6. 스택 top을 start로 하는 티켓이 남아있는 경우 해당 티켓을 routes에서 꺼내고 end를 스택에 삽입
7. 스택이 빌 때까지 5~6번 반복 수행
8. answer을 역순으로 반환

 

 

 

소스코드

def solution(tickets):
    answer = []
    routes = dict() # 티켓 정보를 저장하는 딕셔너리

    for (start, end) in tickets:
        if start in routes:
            routes[start].append(end)
        else:
            routes[start] = [end]
    # 갈 수 있는 공항을 알파벳 역순으로 정렬
    for r in routes.keys():
        routes[r].sort(reverse = True)

    st = ["ICN"]
    while st:
        top = st[-1]
        # 스택 top을 start로 하는 티켓이 없는 경우
        if (top not in routes) or (not routes[top]):
            answer.append(st.pop())   # top을 스택에서 꺼내서 answer에 저장
        # 스택 top을 start로 하는 티켓이 있는 경우
        else:
            st.append(routes[top].pop())

    return answer[::-1]