백준 14889번 스타트와 링크

정답 :

let n = Int(readLine()!)!

var array = Array(repeating: false, count: 100000)
var team1 = 0
var team2 = 0
var score = Array(repeating: Array(repeating: 0, count: n), count: n)
var minValue = Int.max
for i in 0..<n {
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    score[i] = input
}

func dfs(depth : Int, start : Int) {
    if depth == n/2 {
        team1 = 0
        team2 = 0
        for i in 0..<n {
            for j in 0..<n {
                if !array[i] && !array[j] {
                    team2 += score[i][j]
                }
                if array[i] && array[j] {
                    team1 += score[i][j]
                }
            }
        }
        minValue = min(minValue, abs(team1 - team2))
        return
    }
    for i in start..<n {
        if !array[i] {
            array[i] = true
            dfs(depth: depth + 1, start: i)
            array[i] = false
        }
    }
}
dfs(depth: 0, start: 0)
print(minValue)

정답 :

false 배열을 이용하여 스타트팀이 들어간 자리를 true로 변경후 진입한다.

 

그러면 true가 아닌 부분에서 링크팀이 들어간 점수로 계산한다.