[백트래킹 + 구현] 백준 실버2 14889번 스타트와 링크(Swift)

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

14889번: 스타트와 링크

문제풀이

해당 문제는 N명이 주어지면 N/2명을 뽑아 뽑힌 사람과 뽑히지 않은 사람으로 팀을 나눠 팀 간 능력치 차이의 최솟값을 구하는 문제이다.

때문에 문제의 핵심은 N/2명을 뽑아 두 그룹으로 나눠 백트래킹을 사용하여 모든 능력치의 경우의 수를 계산하고 최솟값을 구하는 것이다.

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

백트래킹은 쉽게 말해 깊이 우선 탐색(DFS)에 주로 사용되는 기법이다.

탐색을 하였는데 원하는 값이 아니면 특정 위치로 돌아가 다른 경로로 탐색하는 기법이다.

코드를 보면,

let n = Int(readLine()!)!

var map: [[Int]] = []
map.append(Array(repeating: 0, count: n + 1))

for _ in 0..<n {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  map.append([0] + y)
}

var result = Int.max
var visited = Array(repeating: false, count: n + 1)


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

먼저, visited를 둬 뽑힌 인원과 뽑히지 않은 인원을 구분해 준다.

다음 백트래킹을 위해 dfs메서드를 구현한다.

depth라는 파라미터를 둬 뽑힌 인원을 카운팅 하여 N/2가 뽑혔으면 뽑힌 인원들을 능력치를 계산한다.

이런 식으로 모든 경우의 수를 계산할 수 있다.