여행 경로 - Python, dfs, 히에로홀드 경로(Eulerian Path)

 

 

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

프로그래머스

 

 

 

풀이 - 나의 생각

point 1. 출발지별 도착지를 저장할 때

 

알파벳을 내림차순으로 정렬

 

==> 그래야 pop할때 알파벳 순으로 뽑아낼 수 있음

 

point 2. 기록한 여행 순서를 역순으로 반환

 

이런 기록 문제에 자주 쓰이는 방식

 

DFS 탐색 과정

DFS는 재귀적으로 출발지에서 가능한 도착지로 이동하며 경로를 탐색합니다.

 

1. 가능한 경로가 있으면 계속 깊이 들어갑니다.

2. 더 이상 이동할 경로가 없으면 "후퇴"합니다.

 

후퇴 시, 탐색이 완료된 공항(노드)을 기록해야 경로가 완성됩니다.

 

하지만 이 시점에서 탐색된 노드는 경로의 마지막 부분부터 추가됩니다.

 

따라서 경로는 탐색 중에 자연스럽게 역순으로 쌓이게 됩니다.

 

예시

 

tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]

 

 

 

초기 상태

 

routes = {"ICN": ["JFK"], "JFK": ["HND"], "HND": ["IAD"]}

 

DFS 탐색 과정

시작점 "ICN"에서 출발:

• "ICN" -> "JFK"
• "JFK" -> "HND"
• "HND" -> "IAD"

 

이동 가능한 경로가 없으면 역순으로 기록:

• "IAD" 추가 → 경로: ["IAD"]
• "HND" 추가 → 경로: ["IAD", "HND"]
• "JFK" 추가 → 경로: ["IAD", "HND", "JFK"]
• "ICN" 추가 → 경로: ["IAD", "HND", "JFK", "ICN"]

 

최종 경로 역순 반환

 

DFS 탐색 후 저장된 경로는 역순이므로, 결과를 뒤집으면:

 

["ICN", "JFK", "HND", "IAD"]

 

 

코드

 

from collections import defaultdict

def solution(tickets):
    # 출발지별 도착지 정리
    routes = defaultdict(list)
    for start, end in tickets:
        routes[start].append(end)
    # 도착지 정렬
    for key in routes:
        routes[key].sort(reverse=True)

    # 결과 경로를 저장할 리스트
    path = []

    def dfs(airport):
        # 경로를 모두 소진할 때까지 탐색
        while routes[airport]:
            next_airport = routes[airport].pop()
            dfs(next_airport)
        # 경로를 역순으로 저장
        path.append(airport)

    # DFS 시작
    dfs("ICN")
    return path[::-1]

 

 

 

 

 

 

 

다음에 또 봐요