[코딩테스트] ⚽️ 링크와 스타트 - BJ15661

문제링크

난이도

골드 5

유형

구현, 백트래킹, DFS

소요시간

1시간 - 못품, GPT 도움

회고

백트래킹 문제로 어려워서 GPT 도움을 받음, 복습 필수 문제 페어링 나눌 생각을 못했음

코드

let N = Int(readLine()!)!
var S = Array(repeating: Array(repeating: 0, count: N), count: N)

(0..<N).forEach { i in
    let nums = readLine()!.split(separator: " ").map { Int($0)! }
    (0..<N).forEach { j in S[i][j] = nums[j] }
}

var pair = Array(repeating: Array(repeating: 0, count: N), count: N)
for i in 0..<N {
    for j in i+1..<N {
        pair[i][j] = S[i][j] + S[j][i]
    }
}

var startTeam: [Int] = [0]
var linkTeam: [Int] = []
var startSum = 0
var linkSum = 0
var best = Int.max

func addPair(_ k: Int, _ team: [Int]) -> Int {
    team.reduce(into: 0) { acc, j in
        let a = min(k, j), b = max(k, j)
        acc += pair[a][b]
    }
}

func dfs(_ k: Int) {
    if k == N {
        if !linkTeam.isEmpty {
            best = min(best, abs(startSum - linkSum))
        }
        return
    }

    if k == N - 1 && linkTeam.isEmpty {
        let addL = addPair(k, linkTeam)
        linkSum += addL
        linkTeam.append(k)
        dfs(k + 1)
        linkTeam.removeLast()
        linkSum -= addL
        return
    }

    let addS = addPair(k, startTeam)
    startSum += addS
    startTeam.append(k)
    dfs(k + 1)
    startTeam.removeLast()
    startSum -= addS

    let addL = addPair(k, linkTeam)
    linkSum += addL
    linkTeam.append(k)
    dfs(k + 1)
    linkTeam.removeLast()
    linkSum -= addL
}

dfs(1)
print(best)