14889번: 스타트와 링크

dfs로 풀기

문제 풀이 아이디어

이 문제의 경우 모든 팀의 경우의 수를 따져야 합니다. 따라서 모든 경우의 수를 따질 수 있는 dfs를 통해서 풀어봅니다.

코드

// 점수를 계산하는 함수
func teamScore(of team: [Int]) -> Int {
    var result = 0
    // 점수 더하기 (i == j일 때는 0이므로 예외처리 x)
    for i in team {
        for j in team {
            result += matrix[i][j]
        }
    }
    return result
}

// 입력 받기
let N = Int(readLine()!)!
let teamNumber = Int(N / 2)

// 능력치를 저장하는 이차원 배열
var matrix = [[Int]]()
for _ in 0..<N {
    matrix.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

// 1번 팀인지 아닌지 저장하는 배열 (방문체크배열)
var isTeam1 = Array(repeating: false, count: N)

// 정답 (최솟값이므로 초기값은 Int.max)
var ans = Int.max

// dfs 구현
func dfs(_ depth: Int, _ index: Int) {
    // 한 팀의 멤버 수에 도달하면 점수를 계산한다.
    if depth == teamNumber {
        var score1 = 0
        var score2 = 0
        for i in 0..<N {
            for j in 0..<N {
                if isTeam1[i] && isTeam1[j] { //👉 i와 j가 같이 1번 팀에 소속된 경우
                    score1 += matrix[i][j]
                } else if !isTeam1[i] && !isTeam1[j] { //👉 i와 j가 같이 1번 팀에 소속되지 않은 경우 (= 2번 팀에 소속된 경우)
                    score2 += matrix[i][j]
                }
            }
        }
        ans = min(abs(score1 - score2), ans)
        return
    }
    
    for i in index..<N {
        if !isTeam1[i] {
            isTeam1[i] = true
            dfs(depth + 1, i)
            isTeam1[i] = false
        }
    }
}

dfs(0, 0)
print(ans)

조합으로 풀기

문제 풀이 아이디어

모든 팀의 경우의 수를 구할 때 조합을 사용하면 좀 더 직관적으로 풀 수 있습니다. (다만 코드가 좀 깁니다.)

1. 짤 수 있는 모든 팀의 경우의 수를 조합을 이용해서 구하고
2. 각 조합에 대해서 능력치를 구해서
3. 차이의 최솟값을 출력합니다.

코드

// 조합 구현
func combination(of array: [Int], length: Int) -> [[Int]] {
    var result = [[Int]]()
    
    func combi(index: Int, _ now: [Int]) {
        if now.count == length {
            result.append(now)
            return
        }
        
        for i in index..<array.count {
            combi(index: i + 1, now + [array[i]])
        }
    }
    
    combi(index: 0, [])
    
    return result
}

// 빼기 구현: 1팀 정해지면 2팀의 멤버를 구하기 위해
extension Array where Element == Int {
    static func -(lhs: [Int], rhs: [Int]) -> [Int] {
        lhs.filter { i in
            !rhs.contains(i)
        }
    }
}

// 점수를 계산하는 함수
func teamScore(of team: [Int]) -> Int {
    var result = 0
    // 점수 더하기 (i == j일 때는 0이므로 예외처리 x)
    for i in team {
        for j in team {
            result += matrix[i][j]
        }
    }
    return result
}

// 입력 받기
let N = Int(readLine()!)!

// 멤버 0 ~ N - 1까지 생성
var members = [Int]()
for i in 0..<N {
    members.append(i)
}

// 능력치를 저장하는 이차원 배열
var matrix = [[Int]]()
for _ in 0..<N {
    matrix.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

// 정답 (최솟값이므로 초기값은 Int.max)
var ans = Int.max

// 조합을 통해서 모든 팀의 경우의 수를 구하고 점수를 계산해서 최소한의 차이 구하기
for team in combination(of: members, length: Int(N / 2)) {
    let score1 = teamScore(of: team)
    let score2 = teamScore(of: members - team)
    ans = min(abs(score1 - score2), ans)
}

print(ans)