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

문제 해설

고려해야할점
같인 출발이 있다면 알파벳 순서 (그래서 dfs하기전에 정렬먼저 해줌)
추가 이런노선이 있다면 밑에 작성한 로직으로는 1->2로 가고 종료가 되어버림 1 -> 2 1 -> 3 3 -> 1
문제를 보면 “모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.” 라는 조건이 있기 때문에 모든 도시를 방문할 수 있는것부터가 중요하다.

//실패
func solution(_ tickets:[[String]]) -> [String] {
    var visited: [Bool] = Array(repeating: false, count: tickets.count)
    var startPoint: String = "ICN"
    var result: [String] = [startPoint]

    let arr = tickets.sorted(by: { $0[1] < $1[1] })

    func dfs(_ arr: [[String]]) {
        for i in 0..<tickets.count {
            if arr[i][0] == startPoint && visited[i] == false {
                visited[i] = true
                result.append(arr[i][1])
                startPoint = arr[i][1]
                dfs(arr)
            }
        }
    }

    dfs(arr)

    return result
}

func solution(_ tickets:[[String]]) -> [String] {
   var path: [String] = []
    var answer: [String] = []
    var visited: [Bool] = Array(repeating: false, count: tickets.count)
    let arr = tickets.sorted(by: { $0[1] < $1[1] })

    func dfs(_ depth: Int, _ airport: String, _ ticket: [[String]], _ answer: inout [String], _ visited: inout [Bool], _ path: inout [String]) {
        path.append(airport)

        if depth == ticket.count { answer = path; return }

        for i in 0..<ticket.count where answer.isEmpty {
            let infomation: (start: String, end: String) = (ticket[i].first!, ticket[i].last!)

            if visited[i] == false && airport == infomation.start {
                visited[i] = true
                dfs(depth+1, infomation.end, ticket, &answer, &visited, &path)
                visited[i] = false
            }
        }
        path.removeLast()
    }
    
    dfs(0, "ICN", arr, &answer, &visited, &path)

    return answer
}