Backtracking

[qwerty3345]

9/12

[MUKER-WON]

백트래킹 (Back Tracking)

• 가능한 모든 후보 해를 탐색하면서 해당 경로가 해결책이 아닌 경우 되돌아가는 기법입니다.
• 주로 재귀에서 사용하며 탐색 과정에서 불필요한 경로를 배제하여 효율적으로 문제를 풀 수 있게 도와줍니다.

문제 풀이

백준 15649번:N과 M (1)

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

• 최대한 짧게 풀어본 코드

let I = readLine()!.split { $0 == " " }.map { Int($0)! }
let (N,M) = (I[0],I[1])

func task(_ arr: [Int]) {
    if arr.count == M {
        print(arr.map { String($0) }.joined(separator: " "))
        return
    }
    for i in 1...N where !arr.contains(i) {
        task(arr+[i])
    }
}

task([])

// 약 100ms

• swift에서는 print() 함수가 호출 될 때마다 생각보다 비용이 많이 듭니다. 따라서 print() 문을 한번만 호출 할 수 있게 문자열 변수에 답을 저장해놨습니다.
• 위의 식에서는 arr 배열을 순회하며 같은 숫자가 있는지 검색하기 때문에 비용이 더 들었습니다. 유튜브 강의와 같게 방문처리 배열을 만들어서 풀면 같은 숫자가 있는지 확인하는 조건을 O(1) 만큼의 시간으로 줄일 수 있습니다.

let I = readLine()!.split { $0 == " " }.map { Int($0)! }
let (N,M) = (I[0],I[1])
var visited = Array(repeating: false, count: N+1)
var ans = ""

/// s: 한줄의 숫자 조합 문자열
/// c: s문자열에 들어있는 숫자 개수
func task(_ s: String, _ c: Int) {
    if c == M {
        ans += s+"\n"
        return
    }
    for i in 1...N {
        if !visited[i] {
            visited[i] = true
            task(s+"\(i) ", c+1)
            visited[i] = false
        }
    }
}

task("", 0)
print(ans)

// 약 40ms

백준 9663번: N-Queen

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

• Queen이 모든 행에 하나씩 들어 갈 수 있는 경우의 수를 구하는 문제입니다.
• Queen의 특성상 같은 행,열 및 대각선으로는 Queen을 채울 수 없습니다.
• 그럼 Queen을 놓지 말아야 하는 조건 4개를 살펴보겠습니다.
  • 같은 행: 같은 y축 좌표가 있으면 제외
  • 같은 열: 같은 x축 좌표가 있으면 제외
  • 좌하단 우상단 대각선 : x+y가 같으면 제외
  • 좌상단 우하단 대각선 : x-y가 같으면 제외

let N = Int(readLine()!)!

// true로 있다면 놓을 수 없음
// visited1: 같은 열 검사
// visited2: 좌하단 우상단 대각선 검사
// visited3: 좌상단 우하단 대각선 검사

var visited1 = Array(repeating: false, count: N)
var visited2 = visited1 + visited1
var visited3 = visited2
var ans = 0

/// y: 행의 위치
func task(_ y: Int) {
    if y == N {
        ans += 1
        return
    }
    for x in 0..<N {
        let c = [x, x+y, x-y+N-1] // x-y+N-1 같은 형태가 나오는 이유는 index를 벗어나게 하지 않기 위함

        if !visited1[c[0]] && !visited2[c[1]] && !visited3[c[2]] {
            (visited1[c[0]], visited2[c[1]], visited3[c[2]]) = (true, true, true)
            task(y+1)
            (visited1[c[0]], visited2[c[1]], visited3[c[2]]) = (false, false, false) // 재귀가 풀릴 때 방문처리 해제
        }
    }
}

task(0)
print(ans)

백준 1182번: 부분수열의 합

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

let I = readLine()!.split { $0 == " " }.map { Int($0)! }
let (N,S) = (I[0],I[1])
let arr = readLine()!.split { $0 == " " }.map { Int($0)! }
var ans = 0

/// c: 현재 자릿수
/// sum: 현재까지의 숫자의 합
func task(_ c: Int, _ sum: Int) {
    if c == N {
        if sum == S { ans += 1 }
        return
    }
    task(c+1, sum) // 현재 숫자를 포함하지 않는 조건으로 재귀
    task(c+1, sum+arr[c]) // 현재 숫자를 포함하는 조건으로 재귀
}

task(0,0)
print(S==0 ? ans-1 : ans) // 공집합 처리

[stealmh]

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

여러 선택지가 있으며 이에 따라 게임 결과가 달라지는 예시가 있다고 한다면, 하나의 선택지를 골라 게임을 플레이하고 다시 이전으로 돌아와 다른 결과를 확인하기 위해 다른 선택지를 고르는 것! 모든 선택지를 다 해보는 방법이 백트래킹이다.

백트래킹은 이러한 수읽기에 매우 어울린다! 우리도 바둑이나 오목을 둘 때, 머리속으로 상대의 차례때의 행동을 미리 파악하고 돌을 두지 않는지 생각해보면 바로 이해가능하다! -> 우리의 일상속에서 백트래킹이 많이 녹아있다.

연습문제

N과 M

코드

```swift import Foundation /* 4 2 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. [입력] 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) */ let input = readLine()!.split(separator: " ").map { Int($0)! } let n = input[0], m = input[1] var array = [Int]() func backTracking(_ input: [Int]) { if array.count == m { print(array.map { String($0) }.joined(separator: " ")) return } for i in 1...n { if !input.contains(i) { array.append(i) backTracking(array) array.removeLast() } } } backTracking(array) ```

n queen

코드

```swift import Foundation let n = Int(readLine()!)! var board = Array(repeating: 0, count: n) var count: Int = 0 func backTracking(row: Int) { if row == n { count += 1 return } for col in 0.. row를 +1씩 해주고 있으므로 n이 8이면 가로칸을 0부터 8까지 확인한 것, 즉 한 사이클을 돌았다는 의미로 count를 ++1 해준다. n만큼의 반복문을 진행한다. 이는 세로열이 된다. 백트래킹을 통해 행을 +1해주고 있으니까 우리는 세로열만 반복문을 돌리면 된다 -> 2중for문을 사용하지 않아도 됨을 의미 isValid를 통해 퀸을 넣을 수 있을지 없을지 체크한다. 놓을 수 있다면 row행에 col을 넣어준다. 인덱스는 행, 값은 열을 의미한다. board[3] = 2라면, 3행 2열에 퀸이 있다! 라는 의미 이후 행을 +1해주며 다음 줄을 탐색한다. */ func isValid(row: Int, col: Int) -> Bool { for check_row in 0.. 인자 row와 col은 넣을예정인 퀸의 행,열 만약 보드에 현재 들어가있는 퀸의 열(board[check_row])이 col과 같다면 세로열에 퀸이 2개가 있는 경우이므로 false를 리턴한다. 만약 절대값 열의 차이와 행의 차이가 같다면 대각선에 있다고 확인할 수 있음 -> 즉 넣을예정인 퀸의 위치와 기존에 있는 퀸이 대각선에 위치한다면 이 또한 false를 리턴한다. 이 경우가 아니라면 true를 반환한다! */ backTracking(row: 0) print(count) ```

부분집합

코드

```swift import Foundation let input = readLine()!.split(separator: " ").map { Int($0)! } let n = input[0], s = input[1] var numbers = readLine()!.split(separator: " ").map { Int($0)! } var count: Int = s == 0 ? -1 : 0 func backTracking(_ idx: Int, _ total: Int) { /// ( 인덱스 +1 )가 n이랑 같으면서 if idx == n { /// 총합이 s라면 if total == s { /// 정답 카운트 ++1 count += 1 } return } /// 현재값을 더하지 않는 케이스 backTracking(idx + 1, total) /// 현재값을 더하는 케이스 backTracking(idx + 1, total + numbers[idx]) } backTracking(0, 0) print(count) ```

[qwerty3345]

백트래킹

개념

• 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법.
• 최적화 문제와 결정 문제를 푸는 방법.
• ⭐ 보통 모든 수를 확인해야 하는 경우, for 문의 깊이가 경우에 따라 동적으로 달라질 때 많이 사용!!!
• 재귀적 구조: 주로 재귀함수를 사용하여 해결. 각 상태에서 새로운 후보를 선택하거나 선택하지 않는 방식으로 진행.
• 구현 패턴: 보통 재귀함수 내에서 조건을 만족하는지를 확인하고, 만족하면 다음 단계로 진행하며, 만족하지 않으면 이전 상태로 돌아가 다른 경로를 탐색.
• 가지치기: 불필요한 경로를 조기에 탐색에서 제외하여 효율성을 높이는 기법.

주의사항

• 구현 복잡도: 백트래킹은 구현 난이도가 높고, 특히 실수를 발견하기 어렵기 때문에 꼼꼼한 디버깅과 테스트가 필요.
• 시간 복잡도: 상태 공간이 커질 경우 탐색 시간이 급격히 증가할 수 있음. 가지치기를 적절히 사용해 시간 복잡도를 줄이는 것이 중요.
• 재귀 구조 익숙해지기: 백트래킹은 재귀적 사고가 중요하며, 코드를 작성할 때 함수의 흐름과 상태 변화를 철저히 이해해야 함.

사용 예

• 백트래킹은 모든 가능한 경우의 수를 탐색해야 하거나, 결정 문제에서 특정 조건을 만족하는 해를 찾아야 하는 경우에 많이 사용됩니다. 특히, 탐색 공간이 큰 문제에서 불필요한 탐색을 줄이고 효율적으로 해를 구할 때 유용함

1. 조합 탐색 문제

   • 모든 경우의 수를 찾거나 특정 조건을 만족하는 부분집합을 찾아야 할 때 사용됩니다.
   • 예시: 부분집합의 합 문제, 수열에서 특정 조건을 만족하는 부분집합 구하기.

2. 순열 및 조합 생성 문제

   • 주어진 숫자나 문자에서 가능한 모든 순열이나 조합을 구하는 문제에서 사용됩니다.
   • 예시: N과 M 시리즈 문제 (BOJ 15649), 숫자 배열에서 가능한 모든 순열 생성.

3. N-Queens 문제

   • N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 문제. 체스판의 모든 가능한 배치를 탐색하면서 조건을 만족하는 해를 찾습니다.
   • 예시: N-Queens 문제 (BOJ 9663).

4. 미로 탐색 문제

   • 미로에서 시작점에서 출발해 목적지까지 도달하는 모든 경로를 탐색하는 문제.
   • 예시: 미로의 각 경로를 재귀적으로 탐색하여 최적의 경로 찾기.

5. 그래프 탐색 문제

   • 그래프 상에서 모든 가능한 경로를 탐색해야 할 때, 백트래킹을 사용하여 최적의 경로나 특정 조건을 만족하는 경로를 찾아냅니다.
   • 예시: Hamiltonian Path, 모든 정점을 한 번씩 방문하는 경로 탐색.

6. Sudoku 문제

   • 주어진 수학적 조건을 만족하면서 빈 칸에 숫자를 채워 넣는 문제.
   • 예시: Sudoku 퍼즐에서 모든 가능성을 시도하며 해를 찾는 방식.

요약

백트래킹은 모든 경우의 수를 탐색해야 하거나 결정 문제에서 특정 조건을 만족하는 해를 찾기 위한 상황에서 유용합니다. 순열, 조합, 미로 탐색, N-Queens와 같은 전형적인 문제에서 자주 활용됩니다.

참고한 영상

• 바킹독
• 개발자 장고 - 알기 쉬움!

15649번: N과 M (1)

첫 번째 풀이

```swift let input = readLine()!.components(separatedBy: " ").compactMap { Int($0) } let m = input[0] let n = input[1] // print("m: \(m), n: \(n)") var result: [[Int]] = [] func recr(_ nums: [Int], _ res: [Int]) { // print("res.count == n: \(res.count == n)") // print("res.count: \(res.count) n: \(n)") if res.count == n { // print(res) result.append(res) return } // print("nums: \(nums), res: \(res)") for i in 0..

리팩터링 - 백트래킹 (변형한 데이터를 재귀를 벗어날 때 원상복귀)

```swift let input = readLine()!.components(separatedBy: " ").compactMap { Int($0) } let m = input[0] let n = input[1] var visited: [Bool] = Array(repeating: false, count: m + 1) var result: [Int] = [] func recr(_ depth: Int) { if depth == n { print(result.map(String.init).joined(separator: " ")) return } for number in 1...m { if !visited[number] { visited[number] = true result.append(number) recr(depth + 1) visited[number] = false result.removeLast() } } } recr(0) ```

9663번: N-Queen

• 아직 풀진 못했지만 풀이 형태를 남겨놓자

풀이 방식

``` 1. 카운트 변수를 만든다. (초기 설정값은 0) 2. n*n의 보드를 만든다. 3. 재귀를 돌릴 함수를 만든다. 이때, 매개변수는 0이다. (제일 첫 가로줄의 인덱스를 뜻함) 4. 만약, n과 매개변수가 같으면 카운트를 세고, 리턴한다. - 그 이유는, 가로의 끝까지 재귀가 다 돌아갔을 경우, 성공했다고 보기 때문이다. 5. board의 row 수만큼 반복문을 둔다. 6. board의 제일 첫 번째 칸에 퀸을 둔다. 7. 만약 퀸을 넣었을 때 충돌하지 않는다면, 해당 함수를 재귀로 돌려 다음 줄로 넘어간다. (조건 검사 실행) 8. 그렇지 않다면 뒀던 퀸을 회수한다. 9. 한 칸의 조건 검사가 끝나면 다음 칸으로 넘어간다. 10. 카운트를 리턴한다. ```

[shippingpark]

개념

미연시. 내가 선택한 경로에 대해 끝까지 진입하고, 게임이 종료된다면 (조건에 부합하다면) 선택 이전으로 돌아가 다른 선택.

N과 M (1)

// https://www.acmicpc.net/submit/15649

import Foundation

let input: [Int] = readLine()!.components(separatedBy: " ").map{ Int(String($0))! }
let N = input[0], M = input[1]

var arr = Array(repeating: 0, count: 10) // 결과 값이 담길 배열 [1, 2, 3] <- 첫 번째 조합 예시
var isUsed = Array(repeating: false, count: 10) // index가 곧 키값 (선택된 i에 대한 사용 여부)

func nAndM(k: Int) { // 0<=k<=M // 현재 arr이 뽑힌 상태에 대한 정보
    if k == M { // 만약 모든 숫자가 뽑힌 상황이라면
      for i in 0..<M {
        print(arr[i], separator: " ")
      }
      return
    }

  for i in 1...N {
    if !isUsed[i] {
      arr[k] = i
      isUsed[i] = true // 방문처리
      nAndM(k: k+1) // 1개 뽑힌 상황 대한 실행
      isUsed[i] = false
    }
  }
}

nAndM(k: 0)

N-Queen

• 이 문제에서 어려운 점 - 특정 좌표에 Queen을 둘 수 있는가? 에 대한 판별
• 가지치기가 빈번하면 시간 복잡도 파악이 어렵다
  • 가지치기란 ? 특정 케이스로 인해 검사를 하지 않아도 되는 경로가 생김
  • N이 많이 작아서 백트래킹으로 푸는 문제라면 구현 뒤 가장 오래걸릴 것 같은 케이스를 넣어 반드시 확인
• 시간을 로컬에서 측정할 때는 반드시 Release 모드로 할 것

[사용처리 / 가지치기 / 뒤로 돌아가기 위한 isUsed 활용 규칙]

• 우상단 대각선 규칙성 : x+y가 같다
• 우하단 대각성 규칙성 : x-y가 같다
  • 이 경우 (0, N-1) 상황은 x-y를 바로 index에 넣으면 0이하 값이니 x-y+n-1로 값을 보정한다
• 열은 전부 제외

// MARK: - 백트래킹 (2)
// 백트래킹은 미연시다 ! 단계를 밟고, 엔딩을 마주쳤다면 (base Condtion) 돌아가고, 그 전단계에서 다른 선택지를 골라서 다시금 엔딩을 보는 ...
// 재귀에 이어지는 개념으로, base condition이 필요 (반복을 종료할 조건)
// 재귀에 더해진 점은, path를 탐색할 때 사용 중을 나타내는 isUsed 배열을 생성하여 탐색 노드를 고르고, 끝까지 간 이후엔 사용을 해제함으로서 같은 깊이 내 다음 탐색에서 이전에 사용했던 값들을 사용할 수 있도록 체크

import Foundation

let N = Int(readLine()!)!

var isUsedCol: [Bool] = Array(repeating: false, count: N)
var isUsedCross1: [Bool] = Array(repeating: false, count: 2*N)
var isUsedCross2: [Bool] = Array(repeating: false, count: 2*N)
var result = Int()

func nQueen(cur: Int) { // 사용하려는 현재 좌표 (x 좌표)
  if cur == N {
    result += 1
    return
  }

  for i in 0..<N { // 사용하려는 y 좌표
    guard !isUsedCol[i] && !isUsedCross1[cur+i] && !isUsedCross2[cur-i+N-1] else { continue }
    isUsedCol[i] = true
    isUsedCross1[cur+i] = true
    isUsedCross2[cur-i+N-1] = true
    nQueen(cur: cur+1)
    isUsedCol[i] = false
    isUsedCross1[cur+i] = false
    isUsedCross2[cur-i+N-1] = false
  }
}

nQueen(cur: 0)

print(result)

부분수열의 합

// MARK: - 백트래킹 (3)

// 목표 수량이 정해지지 않고 (3개를 조합하라) 원하는 합산 값이 있는 문제
// 주어진 값을 사용할 지 말 지에 대한 판단으로 트리 분산
// 즉, 그래프의 뎁스는 곧 몇 번째 값에 대한 어떠한 판단인지를 의미 (false/ true)

let input = readLine()!.components(separatedBy: " ").map { Int($0)! }
let N = input[0], S = input[1]
let arr = readLine()!.components(separatedBy: " ").map { Int($0)! }
var result = S != 0 ? 0 : -1

func arrSum(cur: Int, total: Int) {
  if cur == N {
    if total == S {
      result += 1
    }
    return
  }

  arrSum(cur: cur+1, total: total)
  arrSum(cur: cur+1, total: total + arr[cur])
}

arrSum(cur: 0, total: 0)
print(result)

• 메모리 초과 났었던 이유 : N 깊이로 들어갔을 때 종료하는 코드를 조건 충족과 묶어 버렸음

if cur == N && total == S { // 이게 문제 
    result += 1
    return
  }

[개선]

if cur == N {
    if total == S {
      result += 1
    }
    return
  }