[Swift] 프로그래머스(Lv3) - 여행경로

안녕하세요 !

https://programmers.co.kr/learn/courses/30/lessons/43164
오랜만에 코테를 풀어봅니다 ...

풀이

1. tickets를 ticket[1] 오름차순으로 정렬해줍니다.

["ICN", "SFO"], ["ICN", "ATL"] -> ["ICN", "ATL"], ["ICN", "SFO"]

2. ticket을 썼는지 안썼는지 check하는 배열을 만듭니다.

3. DFS로 출발지에서 목적지로 이동합니다.
   1) answer 길이가 tickets.count + 1 이면 답을 다 만든 경우이므로, 종료합니다.
   2) 목적지들 dests를 돌면서 안간곳이면 answer에 추가하고 dfs를 돕니다. 만약 답이 나오면 종료합니다.
   만약 답이 안나왔다면 pop해줘서 원래대로 복구해줍니다.

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    let sortTicket = tickets.sorted { (lhs, rhs) -> Bool in
            return lhs[1] < rhs[1]
        }
    var dict: [String: [(String, Int)]] = [:]
    
    for (idx, ticket) in sortTicket.enumerated() {
        if let _ =  dict[ticket[0]] {
            dict[ticket[0]]!.append((ticket[1], idx))
        } else {
            dict[ticket[0]] = [(ticket[1], idx)]
        }

    }
 
    var check = Array(repeating: false, count: tickets.count)
    
    var answer: [String] = []

    func dfs(_ departure: String) -> Bool {
        if answer.count == tickets.count + 1 {
            return true
        }

        guard let dests = dict[departure] else { return false }

        for dest in dests {
            let index = dest.1
            if !check[index] {
                answer.append(dest.0)
                check[index] = true
                if dfs(dest.0) {
                    return true
                }
                answer.popLast()
                check[index] = false
            }
        }
        
        return false
    }
    
    answer.append("ICN")
    dfs("ICN")
    
    return answer
}