[Swift] 백준 백트래킹 문제 풀이(10971, 14888, 14889)

🥺 이번엔 백트래킹 조지기

https://github.com/tony9402/baekjoon/tree/main/backtracking

해당 링크의 문제들을 도장깨기 하듯? 풀었고 풀이는 주석으로 달아두었습니다. 

 

10971

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

 

💡왜 백트래킹인가?

순회에 필요한 비용을 행렬 형태로 주어지는데, 여기서 차례로 탐색하면서 소요되는 비용을 최소화하는 경우의 수가 너~무 많다.

 

내 풀이

import Foundation

let n = Int(readLine()!)!
var board:[[Int]] = []
var answer = Int(1e9)
var visited = Array(repeating: false, count: n)
// "한번 갔떤 도시로는 다시 갈 수 없다. -> 방문여부 표시"

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

// 백트래킹
// N개의 도시는 무조건 거쳐서 다시 원래의 도시로 돌아옴
func dfs(_ sum: Int, _ depth: Int, _ cur: Int, _ start: Int){
  if cur == start && depth == n { //n개의 도시를 거치고, start와 cur가 일치 -> 다시 원래의 도시로 돌아옴
    answer = min(answer, sum)
    return
  }

  for i in 0..<n { //visited[i]: 안간 도시만 가기
    if !visited[i] && board[cur][i] != 0 { // board[cur][i] : cur에서 i로 갈 때의 비용
      visited[i] = true // cur를 i로 -> i 도시 탐색
      dfs(sum+board[cur][i], depth+1, i, start)
      visited[i] = false
    }
  }
}

dfs(0, 0, 0, 0)
print(answer)

 

14888

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

 

💡왜 백트래킹인가?

연산자를 조합해서 최대, 최소값을 구해야하는데 완전탐색으로 구하기에는 경우의수가 너무 많다.

 

내 풀이

import Foundation

let n = Int(readLine()!)!
let arr = readLine()!.split(separator:" ").map { Int($0)! }
var operator_count = readLine()!.split(separator:" ").map { Int($0)! }

var minValue = 1000000000  // 최소, 최대값 설정할 때 범위를 잘 볼것
var maxValue = -1000000000 // 최소, 최대값은 -10억 ~ 10억 사이

func dfs(_ depth:Int, _ result:Int) {
  if depth == n { // 숫자의 개수가 n일때
    minValue = min(result, minValue)
    maxValue = max(result, maxValue)
    return
  }

  for i in 0..<operator_count.count {
    if operator_count[i] > 0 { // 연산자의 개수가 아직 남아있는 경우
      operator_count[i] -= 1 // 연산자 사용하는걸로 했다가
      switch i {
        case 0:
        dfs(depth+1, result+arr[depth])
        case 1:
        dfs(depth+1, result-arr[depth])
        case 2:
        dfs(depth+1, result*arr[depth])
        default:
        dfs(depth+1, result/arr[depth])
      }
      operator_count[i] += 1 // 다시 안하는걸로 가지치기
    }
  }
}

dfs(1, arr[0]) // 처음수부터 입력인자로 넣기

print(maxValue)
print(minValue)

 

14889

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

 

내 풀이

import Foundation

let n = Int(readLine()!)! //짝수 -> 절반으로 나눠야함
var board:[[Int]] = []

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

// 완탐 or 백트래킹? -
var visited = Array(repeating: false, count:n)
var minValue = Int(1e9)
var star = 0, link = 0

func backtracking(_ depth: Int, _ idx: Int) {
  if depth == n/2 {  // n/2로 좁힌 이유 -> 어차피 절반 뽑으면 나머지 절반은 자동 구성이기 때문
    star = 0
    link = 0
    
    for i in 0..<n {
      for j in 0..<n {
        if visited[i] && visited[j] {
          star += board[i][j] + board[j][i]   // i와 j의 능력치 둘다 더해줘야함
        }

        if !visited[i] && !visited[j] {
          link += board[i][j] + board[j][i]
        }
      }
    }

    minValue = min(minValue, abs(star-link)/2)   // i 와 j - j와 i가 겹치므로 /2를 해줘야함
    
    return
  }

  for i in idx..<n {  // 순열이 아니라 조합이라고 생각하면 13이나 31이나 같으므로 idx부터 시작 (그전은 볼 필요 X)
    if !visited[i] {
      visited[i] = true
      backtracking(depth+1, i+1) // 한명 인원 더 선발하기 (그 전은 볼 필요 없으므로)
      visited[i] = false
    }
  }
}

backtracking(0, 0)
print(minValue)