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

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

 

코드설명 : 

 

이 문제는 팀을 n명중에서 n/2명을 뽑아야된다는게 핵심이다.

그래서 나는 n과 m을 떠올려서 백트래킹 방법으로 팀부터 뽑았다.

 

다음으로, 내가 스타트팀원들을 뽑았으니까 링크팀원들은 자동적으로 스타트팀원들을 뺀 사람들이 되겠다.

스타트팀원들을 n/2명을 뽑으면 맨 아래 for문에서 방문처리가 되게된다. 

그럼 방문처리가 안된 사람들이 링크팀원들인 것이다.

 

n/2명을 뽑았을 때 team1과 team2를 0으로 초기화해준다.(이전에 뽑았던 값을 재사용하게 되는 경우가 없게하기 위함)

그리고 for문으로 arr배열의 전체 인덱스를 돌아주면서 방문하지 않은것은 링크팀(team2)원들이기 때문에 방문하지 않은경우에 team2에 더해주고 방문했다면, 맨 아래에서 뽑은 스타트팀원이기 때문에 team1에 더해준다.

그리고 for문을 탈출하면 team1과 team2를 빼서 최소값을 구해준다.

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

 

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

let n = Int(String(readLine()!))!
var arr = Array(repeating: Array(repeating: 0, count: n), count: n)
var visited = Array(repeating: false, count: n)
var result: [Int] = []
var resultMin = Int.max
var team1 = 0
var team2 = 0
for i in 0..<n {
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr[i] = a
}

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