[백준] BOJ-14889 스타트와 링크

문제

누르면 문제 페이지로 이동합니다.

 

문제 풀이

알고리즘 스터디 1주차 문제로, DFS, 백트래킹 알고리즘으로 접근하며 문제풀이를 시작했다. 

백트래킹은 "DFS를 기반으로 하며, 어느 정도의 Depth 에 도달하면 탐색을 중단 하는 알고리즘" 정도로 이해하고 접근했다.

 

n이 무조건 짝수로 제공되고, 절반 씩 팀을 나누기 때문에 dfs로 순차 탐색을 진행하다가 n / 2 일 경우 탐색을 중단하고

팀원을 구성하도록 했다.

 

두 팀간의 능력치 차이가 가장 적은 경우의 능력치 차이를 출력하는 문제이기에

result 변수의 초기값을 Int.max 로 설정해둔 후, 

min() 과 abs() 함수를 사용해 두 팀 간의 능력치 차이를 구하고 result 와 비교해 더 적은 값으로 업데이트 하도록 했다.

 

import Foundation

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

for i in 0..<n {
    arr[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

func dfs(depth: Int, start: Int) {
    // depth 가 n/2 라는 뜻은 이미 한 팀 구성이 완료 됐다는 뜻
    // 그래서 depth/2 가 되면, 팀구성못한애들을(false) team2에 넣어줌!!
    if depth == n/2 {
        var team1 = 0
        var team2 = 0
        
        for i in 0..<n {
            for j in 0..<n {
                if !visited[i] && !visited[j] { // 방문안한 애들은 team2
                    team2 += arr[i][j]
                }
                if visited[i] && visited[j] { // 방문한 애들은 team1
                    team1 += arr[i][j]  
                }
            }
        }
 
        // 팀 간의 능력치 차이가 더 적으면 기존 result 와 업데이트
        result = min(result, abs(team1 - team2))
        return
    }
    
    // 탐색
    for i in start..<n {
        if !visited[i] {
            visited[i] = true
            dfs(depth: depth + 1, start: i)
            visited[i] = false
        }
    }
}

dfs(depth: 0, start: 0)
print(result)

 

후기

DFS가 알고리즘 문제에서 활용도가 높은 것 같다. 필요할 때 자유자재로  활용 있게 연습해야겠다.