[Programmers] 여행경로 (Swift)

문제 : 

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

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

 

1. 문제 이해하기

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

 

2. 문제 풀이 생각하기

1. 처음에는 tickets의 경로가 String이기 때문에 [String: [String]] 형태의 해시 테이블을 생성하려고 했습니다. 하지만 생각보다 복잡해져서 방법을 바꿨습니다.
2. 결괏값이 모든 티켓을 사용해서 나오는 경로 중 사전 순으로 빠른 경로 하나를 출력하기 때문에 도착지점을 기준 오름차순 정렬을 먼저 하고 시작합니다.
3. dfs를 돌면서 시작점(begin)을 기준으로 tickets[i][0]이 begin이면 해당 경로를 방문 처리하고, 경로(route)에 tickets[i][1]을 append 하고 tickets[i][1]을 기준으로 dfs를 시작합니다.
4. 만약 route의 길이가 tickets의 길이 + 1이면서 ans에 값이 없다면 route를 저장(tickets의 길이 + 1 인 이유는 모든 티켓을 사용해야 하므로 첫 지점 "ICN"을 기준으로 모든 티켓을 사용하면 tickets 길이 + 1이 되기 때문입니다.)
5. dfs가 풀릴 때 해당 티켓의 방문 체크를 없애고 route의 마지막 값을 삭제합니다. (이 이유는 예시로 설명하겠습니다.)
6. 3 ~ 5 반복
7. ans 리턴

 

간단한 예시를 들어보겠습니다.

tickets가 다음과 같이 주어진다고 가정한다면, 정답은 ["ICN", "B", "ICN", "A", "C"]입니다.

이 문제의 경우 만약 티켓 개수만큼 visited를 생성하고 체크한다면, dfs가 풀릴 때, 해당 티켓의 방문 체크를 없애고 route의 마지막 값을 삭제하는 과정을 추가해야 합니다.

그 이유는 지점으로 방문 체크를 하는 것이 아닌, 간선으로 방문을 체크하기 때문입니다.

dfs가 풀릴 때, 방문 체크를 없애고 route의 마지막 값을 삭제하지 않을 경우 해당 문제가 발생할 수 있습니다.

위의 예시에서 "ICN"의 왼쪽 서브 트리를 돌고 오른쪽 서브 트리로 이동할 때, route에 "A"가 남아 있는 상태인 ["ICN", "A"] 상태에서 오른쪽 서브 트리로 넘어갑니다.

따라서 ["ICN", "B", "ICN", "A", "C"]가 아닌 ["ICN", "A", "B", "ICN"]의 결괏값이 출력될 수 있습니다.

 

3. 차근차근 구현하기

import Foundation

var ans = [String]()

func dfs(_ tickets:[[String]], _ visited: [Bool], _ begin: String, _ route: [String]) {
    if tickets.count + 1 == route.count {
        ans = ans == [] ? route : ans
        return
    }
    
    var route = route
    var visited = visited
    
    for i in 0..<tickets.count {
        if !visited[i] && begin == tickets[i][0]{
            visited[i] = true
            route.append(tickets[i][1])
            dfs(tickets, visited, tickets[i][1], route)
            visited[i] = false
            route.removeLast()
        }
    }
}

func solution(_ tickets:[[String]]) -> [String] {
    let visited = Array(repeating: false, count: tickets.count)
    let tickets = tickets.sorted{ $0[1] < $1[1] }
    dfs(tickets, visited, "ICN", ["ICN"])
    
    return ans
}

 

4. 피드백

• dfs 구현에 맛이 들리고 있습니다.