[Swift] 백준_N과 M(1)(15649)

문제

 

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

15649번: N과 M (1)

 

 

풀이

 

백트래킹의 대표 문제를 풀어보려고 했는데, 기존에 dfs라고 생각했던 코드와 동일하게 푸는 것을 보고 헷갈리기 시작했다.

 

백트래킹과 DFS 모두 탐색하는 알고리즘이지만, 백트래킹의 경우는 탐색을 하다가 조건에 맞지 않는다면 더 이상 탐색을 하지 않고 다시 돌아와 다른 노드를 탐색한다.

 

DFS는 모든 경우를 탐색하기때문에 DFS를 이용해 모든 경우를 탐색하다가 불필요한 것들에 대해서는 조건을 추가해서 탐색하지 않도록 구현하면 백트래킹이라고 할 수 있을 것 같다.

다시 말해서, 백트래킹에 DFS가 이용된다고 볼 수 있을 것 같다.

 

 

아무튼 풀이를 보면 arr와 target을 파라미터로 받는 dfs함수를 만들어주었다. target은 입력에서 주어지는 두번째 수를 의미한다.

arr에 숫자를 하나씩 넣으면서 arr의 count가 target과 동일하다면 출력해주도록 하였따.

 

이 함수에서 재귀적으로 dfs를 호출하였는데, 헷갈리지 않기 위해서 과정을 정리해보겠다.

 

4와 2가 입력으로 주어졌을때, 우선 빈 배열이 arr에 들어오면 target과 arr.count가 다르므로 반복문이 실행된다.

이때의 check는 [false,false,false,false]일 것이다.

check[0]이 false이므로 true로 바꾼 뒤에 다시 dfs([1],2)를 호출해준다.

 

DFS를 생각하면 된다. 깊이를 우선으로 탐색하기 때문에 처음의 반복문에서의 i가 1인 경우가 아닌 dfs([1],2)가 먼저 실행된다.

이때 check[0]은 true여서 넘어가고 check[1]은 false이기때문에 numbers[1]인 2가 추가되어 dfs([1,2],2)가 실행될 것이다.

[1,2]의 count는 2와 같으므로 출력된 이후에 함수는 종료된다.

종료되면서 check[1]은 다시 false로 바뀔 것이다. 

 

다시 dfs([1],2)의 반복문으로 돌아가 check[2]가 false이므로 dfs([1,3],2)이 실행될 것이다.

 

이렇게 반복하다보면 문제에서 원하는대로 출력이된다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var numbers = Array(1...input[0])
var check = [Bool](repeating: false, count: input[0])
func dfs(_ arr: [Int], _ target: Int) {
    if arr.count == target {
        print(arr.map { String($0) }.joined(separator: " "))
        return
    }
    for i in 0..<input[0] {
        if !check[i] {
            check[i] = true
            dfs(arr + [numbers[i]], target)
            check[i] = false
        }
    }
}
dfs([],input[1])

 

 

_____________________________________________________________________________________________________

 

이 시리즈 문제를 풀어서 백트래킹을 익혀봐야겠다. 재귀도 헷갈림