[Swift] 백준_스타트와 링크(14889)

문제

 

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

풀이

 

dfs를 이용해  n / 2만큼의 팀원이 차면 계산을 해주도록 하였다.

순서는 상관없으므로 idx라는 파라미터를 이용해 선택된 팀원부터 진행할 수 있도록 하였다. 

 

check[i]를 true로 바꿔주면 count가  n / 2가 된 시점에는 true인 사람 반, false인 사람 반이 돼서 팀이 만들어진다.

 

이후에 반복문을 이용해 true라면 더해주고, false라면 빼주도록 한 뒤에 절댓값을 이용해 기존의 result와 비교해서 더 작은 값을 result에 넣어주었다.

result의 초기값은 임의로 큰 수로 지정하였따.

import Foundation

let n = Int(readLine()!)!
var point: [[Int]] = []
var result = 9999999
var check = Array(repeating: false, count: n)
for _ in 0..<n {
    point.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
func dfs(_ count: Int, _ idx: Int) {
    if count == n / 2 {
        var temp = 0
        for i in 0..<n {
            for j in 0..<n {
                if check[i] && check[j] {
                    temp += point[i][j]
                } else if !check[i] && !check[j] {
                    temp -= point[i][j]
                }
            }
        }
        result = min(result, abs(temp))
        return
    }
    for i in idx..<n {
        if !check[i] {
            check[i] = true
            dfs(count + 1,i)
            check[i] = false
        }
    }
}
dfs(0,0)
print(result)

 

 

_____________________________________________________________________________________________________

 

 

더 나은 방법이 있겠지라는 생각으로 버리는 시간이 많다. 시간초과가 날지라도 일단 구현해보자.