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

문제 링크

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다

문제 이해

이 문제는 그래프 탐색을 활용하여 주어진 항공권을 모두 사용해 여행 경로를 구성하는 문제이다. 항상 ICN 공항에서 출발하며, 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 선택해야 한다.

문제에서 중요한 단서

주어진 항공권을 모두 이용 → 백트래킹(Backtracking)
항공권이 여러 개 주어지므로, 단순히 목적지로 가는 것이 아닌 모든 항공권을 반드시 사용해야 함.
즉, 완전 탐색이 필요하고 한 번 잘못된 경로를 선택하면 다른 경로를 탐색해야 함.
가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return → 우선순위 정렬
예를 들어, ICN → SFO, ICN → ATL 두 개의 선택지가 있을 경우에 무조건 ATL 먼저 가야 함.
즉, 탐색 시 우선순위를 적용해야 하고 사전순으로 빠른 경로를 먼저 선택하는 로직이 필요함.
공항 수는 3개 이상 10,000개 이하 → 최적화(DFS)
최악의 경우에 O(N!)의 시간 복잡도가 필요하며, 시간 초과가 될 수 있음.
즉, 탐색을 최소화하는 최적화가 필요함.

따라서, DFS + 백트래킹 + 우선순위 정렬을 사용해야 함을 알 수 있다.

문제 해결 접근 방법

이 문제는 그래프 탐색을 활용하여 해결할 수 있다. 주어진 문제의 요구사항을 만족시키기 위해 DFS, 백트래킹, 우선순위 정렬을 사용한다.

단계별 접근 방법

출발지를 Key, 목적지를 Value로 하는 인접 리스트 형태로 그래프를 표현
- 예를 들어, 아래와 같이 입력이 주어진다면
```
tickets = [
    ["ICN", "SFO"],
    ["ICN", "ATL"],
    ["SFO", "ATL"],
    ["ATL", "ICN"],
    ["ATL", "SFO"]
]
```
  1. ICN에서 SFO로 가는 항공권 → graph["ICN"] = ["SFO"]
  2. ICN에서 ATL로 가는 항공권 추가 → graph["ICN"] = ["SFO", "ATL"]
  3. SFO에서 ATL로 가는 항공권 → graph["SFO"] = ["ATL"]
  4. ATL에서 ICN으로 가는 항공권 → graph["ATL"] = ["ICN"]
  5. ATL에서 SFO로 가는 항공권 추가 → graph["ATL"] = ["ICN", "SFO"]
  위 과정을 통해 아래와 같은 딕셔너리 형태의 그래프가 생성된다.
```
graph = [
    "ICN": ["SFO", "ATL"],
    "SFO": ["ATL"],
    "ATL": ["ICN", "SFO"]
]
```
```
트리 구조로 표현하면 아래와 같다.

   ICN
  /    \
SFO    ATL
 |     / \
ATL  ICN SFO
```

사전순으로 방문하기 위해 그래프를 정렬한다.

위에 생성된 그래프의 도착지는 아래와 같이 정렬된다.

graph = [
    "ICN": ["ATL", "SFO"],
    "SFO": ["ATL"],
    "ATL": ["ICN", "SFO"]
]

트리 구조로 표현하면 아래와 같다.

     ICN
    /    \
  ATL    SFO
  / \     |
ICN SFO  ATL

DFS를 사용하여 탐색한다.
- 최초 출발지 ICN에서 시작하여 모든 항공권을 사용하는 경로를 탐색한다.
- 핵심은 탐색하면서 항공권을 소모해야한다는 것이다.
- 도착지에서 더 이상 탐색할 곳이 없으면 경로를 저장하고 백트래킹한다.
```
탐색 순서

1. ICN -> ATL
2. ATL -> ICN
3. ICN -> SFO
4. SFO -> ATL
5. ATL -> SFO
```
- 탐색이 끝나면, DFS는 탐색한 경로를 역순으로 저장한다.
  즉, 저장된 결과는 ["SFO", "ATL", "SFO", "ICN", "ATL", "ICN"]이고
  최종 결과는 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]가 된다.

트리 구조 변형 단계

트리 구조의 변형 단계를 통해 조금 더 자세히 알아보자.

최초 입력된 항공권의 트리 구조

   ICN
  /    \
SFO    ATL
 |     / \
ATL  ICN SFO

사전 순으로 정렬된 항공권의 트리 구조

     ICN
    /    \
  ATL    SFO   → 이 레이어가 사전순으로 정렬됨
  / \     |
ICN SFO  ATL   → 이미 정렬되어 있음

ICN의 첫 번째 도착지 ATL를 탐색.

다시 ATL의 첫 번째 도착지인 ICN을 탐색.

ICN의 남은 도착지 SFO를 탐색.

     ICN
    /    \
  ATL     X   → 이 레이어의 SFO가 ICN의 도착지이므로 항공권을 소모한다.
  / \     |
ICN SFO  ATL
 |
SFO

이후 SFO의 유일한 도착지 탐색.

     ICN
    /    \
  ATL     X
  / \     |
ICN SFO   X  → 이 레이어의 ATL이 SFO의 도착지이므로 항공권을 소모한다.
 |
SFO
 |
ATL

마지막으로 ATL의 남은 도착지인 SFO를 탐색.

  ICN
   |
  ATL
  / \
ICN  X  → 이 레이어의 SFO가 ATL의 도착지이므로 항공권을 소모한다.
 |
SFO
 |
ATL
 |
SFO

최종적으로 선형 트리가 완성됨.
```
ICN
 |
ATL
 |
ICN
 |
SFO
 |
ATL
 |
SFO
```

코드 구현 (Swift)

지금까지 알아본 내용을 코드로 구현하면 아래와 같다.

출발지를 Key, 도착지를 Value로 하는 딕셔너리를 생성한다.
목적지 배열을 정렬한다.
DFS로 탐색하며 removeFirst()를 사용하여 항공권을 소모한다.

func solution(_ tickets:[[String]]) -> [String] {
    var graph = [String: [String]]()
    
    // 그래프 딕셔너리 생성
    for ticket in tickets {
        graph[ticket[0], default: []].append(ticket[1])
    }
    
    // 목적지 배열 정렬
    for key in graph.keys {
        graph[key]?.sort()
    }
    
    var route = [String]()
    
    // DFS 탐색
    func dfs(_ airport: String) {
        while let next = graph[airport]?.first {
            graph[airport]?.removeFirst()
            dfs(next)
        }
        route.append(airport)
    }
    
    dfs("ICN")
    return route.reversed()
}

위 코드를 조금 개선하면 아래와 같다.

removeFirst()는 첫 번째 요소를 제거 후 남은 요소의 인덱스를 앞으로 당기는 불필요한 연산이 발생함.
대신 popLast()를 사용하면 마지막 요소를 제거하기 때문에, 인덱스를 앞으로 당기는 연산이 필요 없음.
목적지를 정렬할 때 모든 Key를 확인하며 정렬하는 방법은 비효울적임.
그래프 딕셔너리를 생성할 때, 정렬된 상태로 추가하도록 함.

func solution(_ tickets:[[String]]) -> [String] {
    var graph = [String: [String]]()
    
    // 목적지를 역순으로 정렬하여 추가
    for ticket in tickets.sorted(by: { $0[1] > $1[1] }) {
        graph[ticket[0], default: []].append(ticket[1])
    }
    
    var route = [String]()
    
    func dfs(_ airport: String) {
        while let next = graph[airport]?.popLast() {  // 불필요한 연산 제거
            dfs(next)
        }
        route.append(airport)
    }
    
    dfs("ICN")
    return route.reversed()
}

만약 Swifty한 코드가 좋다면, 아래처럼 작성할 수도 있다.

func solution(_ tickets:[[String]]) -> [String] {
    var graph = Dictionary(grouping: tickets, by: { $0[0] })
        .mapValues { $0.map { $0[1] }.sorted(by: >) }
    
    var route = [String]()
    
    func dfs(_ airport: String) {
        while let next = graph[airport]?.popLast() {
            dfs(next)
        }
        route.append(airport)
    }
    
    dfs("ICN")
    return route.reversed()
}