[PS] 백트래킹 20문제 풀기 - 0. 개념, 1. n과m(1) ~ (4)

앞으로 4/17~23 이번주는 백트레킹 문제만 조지기로 다짐했다. 이번주 20문제를 풀고 익혀보자.

이번주 헤치울 문제들 https://www.acmicpc.net/step/34

 

 

백트레킹 개념 정리

모든 경우의 수를 전부 고려하는 알고리즘으로 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘

모든 경우의 수를 전부 다 고려하는 브루트포스 (완전탐색)보다 더 시간을 절약할 수 있다.

 

완전탐색의 대표적인 방법 중 하나가 DFS로, 재귀를 이용해서 현재시점에서 방문할 곳을 탐색하고 방문한다.

반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색해서 가지치기라고 부른다.

 

백트레킹은 BFS나 DFS와 함께 구현한다. 그러나 해당 노드가 조건에 부합하지 않으면 이전 노드로 돌아가야 하기 때문에 BFS보다 DFS가 더 편하다. 백트레킹에서 중요한 것은 한정 조건이다. 조건을 잘 걸어서 완전탐색에서 유망하지 않은 시도를 걸러내는 것이 중요하다.

 

푸는 방법은

1. 한정조건을 적용하고, 2. DFS를 통해서 전체 탐색을 진행

 

1. n과m(1)

n과m(1) 문제에서는 한정조건이 무엇인가?

-> 1~N 사이 수 중에서 중복없이 M개 고르기 

이미 뽑은 수라면, 뽑지 않는 것이 바로 한정조건이다. 

그리고 배열에 추가 시에 해당 배열의 길이가 m과 같으면 재귀를 멈춘다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]
var answer = [Int]()

func backtracking() {
    // 숫자 길이가 m이랑 같으면 더해서 반환
    if answer.count == m {
        answer.map { print($0, terminator: " ") }
        print()
        return
    }
    
    for i in 1...n { // 1부터 n까지 돌면서
        if !answer.contains(i) { // 조건을 작성
            answer.append(i)
            backtracking()
            answer.popLast()
        }
    }
}

backtracking()

 

 

---

2. n과m(2)

n과m(2) 문제는 한정조건이 추가됐다.

중복없고 + 오름차순이어야 한다는 것.

조건을 추가해보자.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]
var answer = [Int]()

func backtracking() {
    // 숫자 길이가 m이랑 같으면 더해서 반환
    if answer.count == m {
        answer.map { print($0, terminator: " ") }
        print()
        return
    }
    
    for i in 1...n { // 1부터 n까지 돌면서
        if !answer.contains(i) { // 중복X
            if answer.last ?? 0 < i {
                answer.append(i)
                backtracking()
                answer.popLast()
            }
        }
    }
}

backtracking()

 

---

3. n과m(3) 시간초과 이슈 - 매번 print 방식 대신 string에 더해서 출력할 것!

- 중복 상관없다!

 

import Foundation

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]

var answer = [Int]()
var answerString = ""

func backtracking() {
    if answer.count == m {
        answerString += answer.map { String($0) }.joined(separator: " ")
        answerString += "\n"
        return
    }
    
    for i in 1...n {
        answer.append(i)
        backtracking()
        answer.removeLast()
    }
}

backtracking()
print(answerString)

조건은 더 쉬웠는데 시간초과가 났다. print를 조건에 맞을 때마다 출력하는 것이 문제였다.

대신에 string 변수를 만들어서 더해주는 방식으로 구현하니까 해결

 

 

---

4. n과m(4)

- 중복 상관없고, 대신 오름차순!

import Foundation

let nm = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nm[0]
let m = nm[1]

var answer = [Int]()

func backtracking() {
    if answer.count == m {
        answer.map { print($0, terminator: " ") }
        print()
        return
    }
    
    for i in 1...n {
        if answer.last ?? 0 <= i {
            answer.append(i)
            backtracking()
            answer.removeLast()
        }
    }
}

backtracking()

 

 

---

새로운 지식

removeLast()는 값이 무조건 존재해야하고,

popLast()는 값이 없으면 nil을 리턴한다는 차이점이 있다.

var array = ["RU", "HEE"]에서 
array.removeLast() "HEE" 반환 
array.removeLast() "RU" 반환
array.removeLast() -> crash 발생

array.popLast() Optional("HEE") 반환 
array.popLast() Optional("RU") 반환
array.popLast() Optional(nil) 반환