[Algorithm] 여행경로

[hwangJi-dev]

💬 문제

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

💬 Idea

• 재귀함수 호출 방식을 활용하여 여행 경로를 짜자!
• 사용한 티켓을 다시 사용하는 일이 없어야 하므로 visited 배열을 만들어 티켓의 사용 여부를 저장한다.
• 여행 경로는 알파벳 순서가 앞서는 경로 순이어야 하므로 처음에 tickets 배열을 사전순으로 정렬한 뒤 순회한다.
• 이후 “ICN” 인천공항을 출발지점으로 시작하여 순회하여 여행 경로를 구한다.

💬 풀이

import Foundation

func solution(_ tickets: [[String]]) -> [String] {
    let tickets = tickets.sorted(by: { $0[1] < $1[1] })
    var ans: [String] = []
    var visited = Array(repeating: false, count: tickets.count)
    
    func dfs(_ start: String) {
        if tickets.count == ans.count {
            ans.append(start)
            return
        }
        
        for i in 0..<tickets.count {
            if !visited[i] && tickets[i][0] == start {
                visited[i] = true
                ans.append(tickets[i][0])
                dfs(tickets[i][1])

                if ans.count == tickets.count + 1 {
                    return
                }
                
                visited[i] = false
                ans.removeLast()
            }
        }
    }
    
    dfs("ICN")
    return ans
}