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

문제 풀이 아이디어

전형적인 완전 탐색 문제로 보입니다. 하지만 기본에 풀었던 문제들과는 조금씩 다른 부분들이 있습니다.

1. 모든 “공항"을 방문해야 하는 것이 아니라 모든 “티켓"을 사용해야 합니다. 따라서 방문 체크 배열이 아니라 티켓 사용 배열을 만들어서 체크해야 합니다.
2. 알파벳 순으로 가장 앞선 경로를 찾아야 하므로 목적지를 알파벳 수능로 정렬해야 합니다.
3. 경로를 1개만 찾으면 됩니다. 경로를 찾았다면 탐색을 멈추어야 합니다. (back tracking)

코드

func solution(_ tickets:[[String]]) -> [String] {
    
    // 알파벳 순으로 이동하기 위해서 ticket의 목적지를 알파벳 순으로 정렬한다.
    let tickets = tickets.sorted(by: { $0[1] < $1[1] })
        //👉 argument와 동일한 이름의 변수를 선언할 수 있다.
    
    // 티켓 사용 여부
    var used = Array(repeating: false, count: tickets.count)
    
    // 출발지를 미리 넣어둔다.
    var result = ["ICN"]
    
    //dfs 구현
    func dfs(_ from: String) {
       
        // 모든 ticket을 순환하면서
        for i in 0..<tickets.count {
            // 현재 공항에서 출발할 수 있는 티켓이고 아직 사용안함
            if tickets[i][0] == from && used[i] == false {
                used[i] = true
                result.append(tickets[i][1])
                dfs(tickets[i][1])
                
                // 중간에 이미 모든 티켓을 사용했으면 더 이상 탐색이 필요 없음 (back tracking)
                if result.count == tickets.count + 1 {
                    return
                }
                
                used[i] = false
                _ = result.removeLast()
            }
        }
    }
    
    dfs("ICN")
    
    return result
}