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

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

프로그래머스

 

1. 문제 이해

• "ICN" 공항에서 출발한다.
• 주어진 항공권은 모두 사용해야 한다.
• 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택해야 한다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

 

위 조건을 고려하여 방문하는 공항 경로를 출력하자

 

 

 

 

2. 접근 방법

• "가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택해야 한다." -> [a, b]에서 b를 기준으로 오름차순 정렬
• visited와 백트래킹을 사용한 dfs

 

 

func solution(_ tickets:[[String]]) -> [String] {
    let tickets = tickets.sorted{$0[1] < $1[1]} // 알파벳 순서 오름차순
    var visited = [Int]()
    var result = [String]()

    func dfs(cur: String){
        if visited.count == tickets.count{
            result.append(cur)
            return
        }
        
        for (offset,ticket) in tickets.enumerated(){
            if cur == ticket[0]{
                if !visited.contains(offset){
                    
                    result.append(cur)
                    visited.append(offset)
                    
                    dfs(cur: ticket[1])
                    
                    if visited.count == tickets.count{ // 주어진 항공권을 모두 사용한 경우 리턴
                        return
                    }
                    
                    result.removeLast()
                    visited.removeLast()
                }
            }
        }
    }
    dfs(cur: "ICN") // 출발 경로 ICN
    return result
}