여행 경로 문제 해결하기 (DFS와 그래프 탐색)

문제 개요

여행 경로를 정하는 문제로, 항공권 정보를 바탕으로 "ICN"에서 출발하여 모든 항공권을 사용하면서 경로를 찾는 과정을 다룹니다.
특히, 여러 경로가 가능할 경우 알파벳 순서로 가장 앞서는 경로를 반환해야 합니다.

핵심 문제 해결 접근법

티켓 정보를 그래프 형태로 변환:
출발 공항을 키(key), 도착 공항 리스트를 값(value)으로 저장하는 인접 리스트로 그래프를 표현.

알파벳 순서에 따른 우선순위 설정:
도착 공항 리스트를 사전순으로 정렬하여 우선적으로 탐색할 경로를 설정.

텍스트DFS(깊이 우선 탐색):
한 공항에서 가능한 도착지로 이동하며 경로를 탐색.
모든 티켓을 사용해야 하므로 탐색 완료 후 역순으로 경로를 기록.

결과 경로 반환:
DFS로 탐색하며 생성된 경로를 역순으로 정렬해 반환.

코드 구현

import Foundation

func solution(_ tickets: [[String]]) -> [String] {
    // 1. 티켓 정보를 그래프 형태로 변환
    var graph = [String: [String]]()
    for ticket in tickets {
        let from = ticket[0]
        let to = ticket[1]
        graph[from, default: []].append(to)
    }
    
    // 2. 각 공항의 도착지를 알파벳 순으로 정렬
    for key in graph.keys {
        graph[key] = graph[key]?.sorted()
    }
    
    // 3. DFS를 활용하여 경로 탐색
    var path: [String] = []
    func dfs(_ airport: String) {
        // 더 갈 곳이 있는 경우
        while let destinations = graph[airport], !destinations.isEmpty {
            // 알파벳 순서로 가장 앞선 경로를 탐색
            let next = graph[airport]!.removeFirst()
            dfs(next)
        }
        path.append(airport)  // 더 이상 갈 곳이 없으면 경로에 추가
    }
    
    dfs("ICN")  // 항상 "ICN"에서 시작
    return path.reversed()  // 경로를 뒤집어서 반환
}

코드 동작 설명

그래프 생성:
graph는 딕셔너리를 활용하여 출발 공항을 키로, 도착 공항 리스트를 값으로 저장.
예를 들어:

graph = [
    "ICN": ["JFK", "SFO"],
    "JFK": ["HND"],
    "HND": ["IAD"]
]

도착지 정렬:
각 공항의 도착지를 사전순으로 정렬하여 경로 탐색의 우선순위를 설정.

정렬된 그래프:

graph = [
    "ICN": ["JFK", "SFO"],
    "JFK": ["HND"],
    "HND": ["IAD"]
]

DFS 탐색:
DFS를 활용하여 출발 공항에서 도착 공항으로 이동하며 모든 티켓을 사용.
재귀 호출로 깊이 우선 탐색을 수행하며 더 이상 갈 곳이 없으면 경로를 저장.
경로 반환:
탐색 결과는 역순으로 저장되므로 path.reversed()를 통해 올바른 경로를 반환.

예제 실행

let tickets1 = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]
let tickets2 = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]

print(solution(tickets1))  // 출력: ["ICN", "JFK", "HND", "IAD"]
print(solution(tickets2))  // 출력: ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

출력 결과
Example 1:
경로: ICN → JFK → HND → IAD.
최종 경로: ["ICN", "JFK", "HND", "IAD"].

Example 2:
가능한 경로:
ICN → SFO → ATL → ICN → ATL → SFO
ICN → ATL → ICN → SFO → ATL → SFO
알파벳 순으로 앞서는 경로 선택:
최종 경로: ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"].

학습 포인트

그래프 탐색:
티켓 데이터를 그래프로 변환하여 문제를 구조화.
깊이 우선 탐색(DFS)을 활용해 경로를 찾는 기법.

우선순위 관리:
도착지를 알파벳 순으로 정렬하여 조건에 맞는 최적의 경로 선택.

재귀 호출:
DFS를 재귀적으로 구현하여 탐색 과정을 간결하게 표현.

역순 처리:
DFS의 특성상 경로는 역순으로 쌓이므로 최종적으로 뒤집어 반환.

느낀 점

이 문제를 통해 그래프 탐색과 경로 최적화를 깊이 이해할 수 있었습니다.
특히, 조건(알파벳 순서)을 만족하는 경로 탐색은 정렬과 데이터 구조의 중요성을 다시금 상기시켰습니다.
앞으로 더 복잡한 그래프 탐색 문제에서도 적용할 수 있는 기초를 다진 것 같습니다.