[Swift][BruteForce] 백준 15661번 (링크와 스타트)

요구능력 : 백트래킹에 대한 이해

 

코드설명 : 

 

스타트와 링크와 문제가 조금 다르긴하지만 똑같은 방식으로 풀었는데, 맞았다.

설명이 필요하신분은 스타트와 링크를 봐주세요.

스타트와 링크와 다른점은 이 문제에는 N이 홀수로도 들어온다는 것이다.

스타트와 링크 코드를 링크와 스타트에 넣으면 틀렸다고 나오는데.. 이유는 모르겠고

 

똑같이 풀어도 맞을 수 밖에 없는 이유를 적어보자면,

두팀의 능력치를 빼서 작은값이 나오는 경우는 두 팀이 그래도 인원수가 비슷한경우에 이루어진다.

만약 5명이라면, 2명 3명 이런식이다.

그래서 depth가 n/2인 경우에 멈춰도 되는거다.

 

후기 : 막 어려운건 아니지만, visited가아니고 딴 배열에 저장해서 찾느라 시간 좀 걸렸다.

let n = Int(String(readLine()!))!
var arr: [[Int]] = [[]]
var visited = Array(repeating: false, count: n + 1)
var result = Int.max

for _ in 1...n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func dfs(_ depth: Int, _ start: Int){
    if depth == n / 2{
        var startTeam = 0
        var linkTeam = 0
        for i in 1...n{
            for j in 1...n {
                if !visited[i] && !visited[j] {
                    linkTeam += arr[i][j - 1]
                }
                if visited[i] && visited[j] {
                    startTeam += arr[i][j - 1]
                }
            }
        }
        result = min(result, abs(startTeam - linkTeam))
        return
    }
    for i in start...n {
        if !visited[i] {
            visited[i] = true
            dfs(depth + 1, i)
            visited[i] = false
        }
    }

}
dfs(0, 0)

print(result)