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

문제 설명

백준 14889번 문제 링크

입력 및 출력

» 입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

» 출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입출력(테스트케이스)

입력	출력
4 0 1 2 3 4 0 5 6 7 1 0 2 3 4 5 0	0
6 0 1 2 3 4 5 1 0 2 3 4 5 1 2 0 3 4 5 1 2 3 0 4 5 1 2 3 4 0 5 1 2 3 4 5 0	2
8 0 5 4 5 4 5 4 5 4 0 5 1 2 3 4 5 9 8 0 1 2 3 1 2 9 9 9 0 9 9 9 9 1 1 1 1 0 1 1 1 8 7 6 5 4 0 3 2 9 1 9 1 9 1 0 9 6 5 4 3 2 1 9 0	1

문제 힌트

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ14889_SWIFT
//
//  Created by choiyoujun on 2022/02/22.
//

let N = Int(readLine()!)!
var S = Array<[Int]>(repeating: [Int](repeating: 0, count: N + 1), count: N + 1)
var check = [Bool](repeating: false, count: N + 1)

for i in 1...N {
    let arr = readLine()!.split(separator: " ").map{ Int($0)! }
    
    for j in 1...N {
        S[i][j] = arr[j - 1]
    }
}

var res = Int.max
var ST = 0
var LT = 0

func dfs(depth: Int, start: Int) -> Void {
    if depth == N / 2 {
        ST = 0
        LT = 0
        
        for i in 1...N {
            for j in 1...N {
                if !check[i] && !check[j] {
                    ST += S[i][j]
                }
                
                if check[i] && check[j] {
                    LT += S[i][j]
                }
            }
        }
        
        res = min(res, abs(ST - LT))
        return
    }
    
    for i in start...N {
        if !check[i] {
            check[i] = true
            dfs(depth: depth + 1, start: i)
            check[i] = false
        }
    }
}

dfs(depth: 0, start: 1)
print(res)