[Programmers 알고리즘 고득점 Kit] 여행 경로[Python]

문제

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

프로그래머스

 

 

---

풀이

항공권의 정보가 주어졌을 때, 모든 공항을 전부 방문할 수 있는 경우를 찾고 들른 공항의 순서를 출력하는 문제다.

정답이 여러개 존재하는 경우 공항의 순서를 사전순으로 출력해야 한다.

일단, 입력받은 항공권의 정보에 대해 다음과 같이 그래프를 생성하고, 역순으로 정렬해줬다.

from collections import defaultdict

def solution(tickets):
    graph = defaultdict(list)
    for u, v in tickets:
        graph[u].append(v)
    for key in graph.keys():
        graph[key].sort(reverse=True)

역순으로 정렬한 이유는, pop()으로 빠르게 사전순으로 공항을 방문하기 위함이다 모든 도시를 방문할 수 없는 경우는 주어지므로, DFS를 진행했을 때 만약 더 이상 방문할 공항이 없다면 탐색이 끝났음을 알 수 있다.

"ICN" 부터 시작하며, 마지막 공항까지 방문 후, 결과 배열에 마지막에 방문한 공항을 넣어주자.

    path = ["ICN"]
    res = []
    while path:
        cur = path[-1]
        if len(graph[cur]) > 0:
            path.append(graph[cur].pop())
        else :
            res.append(path.pop())

res 에는 사전역순으로 마지막에 방문한 공항들이 담겨져 있다.

이를 반전해서 반환하면 사전순으로 순서대로 방문한 공항 리스트를 얻을 수 있다.

    return res[::-1]

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/Programmers/Coding%20Test%20High%20Score%20Kit/DFS%2BBFS/%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C.py