[Swift] 백준 10971 - 외판원 순회2

문제 바로가기

이 문제를 풀면서 알아야할 점은

• 깊이를 알 수 없는 for문을 돌아야함 -> 재귀함수
  • 재귀함수의 종료 조건은 '현재도시 == 출발 도시'과 'result배열의 원소 개수 == n'이다.
• 어떤 도시에서 출발하든 최소값은 같다 -> 특정 도시에서 시작하는 경우만 고려해도 된다

이 두 아이디어만 가지면 조금 풀이가 쉬워진다..!!

최종 풀이

import Foundation

let n = Int(readLine()!)!
var W = Array(repeating: Array(repeating: 0, count: n), count: n)

for i in 0..<n {
    let a = readLine()!.split(separator:" ").map {Int(String($0))!}
    W[i] = a
}

var minSum = 10000000
var result = [Int]()
var mode = Array(repeating: true, count: n)

func recur(_ present: Int, _ destination: Int) {
    if result.count == n && present == destination {
        minSum = min(minSum, result.reduce(0, {$0+$1})
        return
    }
    
    for i in 0..<n {
        if mode[i] == true && W[present][i] > 0 {
            result.append(W[present][i]
            mode[i] = false
            recur(i,destination)
            result.removeLast()
            mode[i] = true
        }
        
    }
}

recur(0,0)
print(minSum)

• recur(1,1)또는 recur(2,2) 등을 넣어도 값은 항상 같다
• 문제에서 행렬의 성분은 1000,000 이하이고, 2<= N <= 10 이라고 명시하였기 때문에 minSum을 가능한 최대값인 10000000으로 하였다.