[Swift]프로그래머스-여행 경로(DFS) 문제 풀이 정답 답안

출처: https://icksw.tistory.com/228

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

 

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    
    //도착지를 기준으로 티켓을 알파벳순으로 정렬.
    let tickets = tickets.sorted { $0[1] < $1[1]}
    //티켓 사용 여부를 저장할 배열
    var visited = [Bool](repeating: false, count: tickets.count)
    
    var result: [String] = []
    
    func dfs(start: String) {
        
        if result.count == tickets.count {
            result.append(start)
            return
        }
        
        for i in 0..<tickets.count {
            
            if tickets[i][0] == start && !visited[i] { 
                //티켓 사용
                visited[i] = true
                //경로 저장
                result.append(start)
                //dfs로 경로 탐색
                dfs(start: tickets[i][1])
                if result.count == tickets.count + 1 {
                    return
                }
                result.removeLast()
                visited[i] = false
            }
        }
    }
        
    dfs(start: "ICN")
    return result
}