[Algorithm/Programmers] 여행 경로(DFS/BFS)

제한 사항:

1. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. -> 목적지의 알파벳 순으로 정렬한다.

2. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. -> 모든 경로를 지나가지만 모든 경로가 이어져 있는 것은 아니다.

3. 주어진 항공권은 모두 사용해야 합니다. 

4. 항상 ICN에서 출발한다.

 

코드: 

import Foundation

func solution(_ tickets:[[String]]) -> [String] {
    
    var visited = Array(repeating: false, count: tickets.count)
    var start = "ICN"
  
    let sortedTickets = tickets.sorted(by: { $0[1] < $1[1] })
    var route = [String]()
    var result = [String]()
    print(sortedTickets)
    func dfs(_ cnt: Int, _ visited: inout [Bool], _ start: String) {
        route.append(start)
        if cnt == tickets.count {
            result = route
            return
        }
        if result.isEmpty {
            for i in 0..<tickets.count {
                if sortedTickets[i][0] == start, !visited[i] {
                    visited[i] = true
                    dfs(cnt+1, &visited, sortedTickets[i][1])
                    visited[i] = false
                }
            }
        }
        route.removeLast()
    }
    dfs(0, &visited, start)
    return result
}
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]))

2번 조건을 충족하기 위한 테스트 케이스: 

tickets = [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]

 

문제: 

https://programmers.co.kr/learn/courses/30/lessons/43164?language=swift

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