Swift) 프로그래머스 여행경로 - Lv. 3

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

프로그래머스

문제 풀이: DFS로 모든 티켓을 소비한 경우에만 유효한 경로인 문제. 모든 노드가 연결되어야 하고 사전순으로 가장 빠른 경로가 답이므로, 티켓 배열을 정렬한 후 dfs로 출발하는 노드를 찾은 후 path에 추가한 후 다시 해당 함수를 호출하는 식으로 문제를 해결. 

import Foundation

func dfs(_ ticket: [[String]], path: [String]) -> [String] {
    if ticket.count == 0 {
        return path
    }
    var validIndex = -1
    for i in 0..<ticket.count {
        if ticket[i][0] == path.last {
            validIndex = i
            break
        }
    }
    if validIndex == -1 {
        return []
    }
    
    while ticket[validIndex][0] == path.last {
        var nextTicket = ticket
        let removeNode = nextTicket.remove(at: validIndex)
        var cpPath = path
        cpPath.append(removeNode[1])
        var nextPath = dfs(nextTicket, path: cpPath)
        if nextPath != [] {
            return nextPath
        }
        validIndex += 1
    }
    return []
}

func solution(_ tickets:[[String]]) -> [String] {
    let sortedTickets = tickets.sorted { one, two in
        if one[0] == two[0] {
            return one[1] < two[1]
        }
        return one[0] < two[0]
    }
    return dfs(sortedTickets, path: ["ICN"])
}