[백준] (Swift) 14889번 - 스타트와 링크 (DFS-백트래킹)

문제링크

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

문제풀이

해당 문제를 풀기 위해서는 완전탐색으로 풀거나, 백트래킹이라는 개념을 이용하는 방법이 있다고 한다. 완전탐색은 말그대로 그래프 전체를 탐색해서 팀원이 됐는지, 안됐는지 판단하는 방법이고, 백트래킹은 "DFS 방법이지만, 어느정도의 depth에 도달하게 되면 탐색중지"하는 알고리즘이다. 백트래킹에 대한 개념을 잘 모르니, 이 문제를 포스팅한 후 백트래킹과 관련한 알고리즘 포스팅을 할 예정이다.

우선 나는, 백트래킹이 뭔진 모르겠고!! dfs를 구현하지만, 일정 숫자가 된다면,  팀원 구성을 멈추고 차이를 구했다. (이게바로 백트래킹!!)

 

1. 팀구성을 위한 변수 설정

• n : 입력받는 변수 
• s : 입력받는 능력치
• visited : 방문처리 (팀 구성이 완료된 것은 true, 아닌것은 false로 둘 예정)
• team1 : team1이 된 사람들의 능력치 합
• team2 : team2가 된 사람들의 능력치 합
• minResult : 작은 값을 계속해서 갱신할 예정, (초반은 큰수 임의로 설정)

let n = Int(String(readLine()!))!
var s = Array(repeating: Array(repeating: 0, count: n), count: n)
var visited = Array(repeating: false, count: n)
var team1 = 0
var team2 = 0
var minResult = 99999

 

2. dfs 함수

• i부터 탐색하면서 visited 에 true 로 바꾸면서 탐색

for i in start..<n {
    if !visited[i] {
        visited[i] = true
        dfs(depth: depth + 1, start: i)
        visited[i] = false
    }
}

 

• depth 가 n/2 가 되는 순간, dfs의 탐색은 중지할 것이다. 그래서 if 문을 dfs 함수 내부 최상단에 위치시킴
• 계속해서 갱신되어서 갑싱 변하는 team1과 team2 를 초기화 시켜주고, 
• for 문을 돌려서 방문했던 (true)인 애들은 team1로, 방문하지 않았던 (false)인 애들을 team2로 보내면서 능력치값을 더해줌
• 마지막으로 team1에서 team2를 뺀 절댓값을 minResult에 비교해서 넣어줌.

// depth 가 반이됐다는 뜻은 이미 한 팀 구성이 완료 됐다는 뜻
// 그래서 depth/2 가 되면, 팀구성못한애들을(false) team2에 넣어줌!!
if depth == n/2 {
    team1 = 0
    team2 = 0
    for i in 0..<n{
        for j in 0..<n{
            if !visited[i] && !visited[j]{
                team2 += s[i][j]
            }
            if visited[i] && visited[j] {
                team1 += s[i][j]
            }
        }
    }
    // 그리고 팀구성이 완료된 애들의 차를 구해서 min값을 계속 갱신시켜주자
    minResult = min(minResult, abs(team1 - team2))

 

 

💻 최종 코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/14889_%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80%20%EB%A7%81%ED%81%AC/main.swift

GitHub - deslog/Algorithm

let n = Int(String(readLine()!))!
var s = Array(repeating: Array(repeating: 0, count: n), count: n)
var visited = Array(repeating: false, count: n)
var team1 = 0
var team2 = 0
var minResult = 99999

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

func dfs(depth: Int, start: Int) {
    // depth 가 반이됐다는 뜻은 이미 한 팀 구성이 완료 됐다는 뜻
    // 그래서 depth = n/2 가 되면, 팀구성못한애들을(false) team2에 넣어줌!!
    if depth == n/2 {
        team1 = 0
        team2 = 0
        for i in 0..<n{
            for j in 0..<n{
                if !visited[i] && !visited[j]{
                    team2 += s[i][j]
                }
                if visited[i] && visited[j] {
                    team1 += s[i][j]
                }
            }
        }
        // 그리고 팀구성이 완료된 애들의 차를 구해서 min값을 계속 갱신시켜주자
        minResult = min(minResult, 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(minResult)