[백준] (Swift) 15649번 - N과 M(1) (feat. DFS, 백트래킹)

🟠 문제

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

15649번: N과 M (1)

 

🟠 내가 푼 풀이

처음에 문제를 보고 감을 잡지 못했다. 완전탐색으로 방문 여부를 탐색해서 출력해주어야하나? 고민했다. (코테스터디에서 풀었던 문젠데 전혀 기억이 나질 않았다.)

결국 어떤 알고리즘을 사용했는지 힌트를 얻고자 인터넷을 조금 찾아보았다. DFS와 백트래킹 개념을 이용하는 것으로 보였다.

문제를 풀어보면, 왜 DFS로 푸는지는 이해가 되는데, 백트래킹 개념이 들어간게 맞는지 이해가 되지 않는다. 재귀를 돌다가 현재 내가 진행하고 있는 i 에 대해서 포함여부를 판단하는 과정이 백트래킹인건가?  (백트래킹 = 완전탐색을 하지 않고 어느 조건을 정해서 조건을 만족하지 않으면 탐색하지 않는 것) 이라는 개념을 되새겨보면 맞을 수도..?

재귀로 DFS를 푸는것이 익숙하지 않아서 그림을 차근차근 그리면서 코드를 해석하면서 문제를 풀었다.

설계를 해보면 다음과 같다.  재귀는,,, 돌아 돌아 순회하는 것이 많기 때문에 잘 생각해야 풀린다... (아직 너무 부족하다 ㅎ헤ㅔ헤)

이 것을 그대로 코드로 옮기면 다음과같다.

 

🟠 정답코드

var nm = readLine()!.split(separator: " ").map{ Int($0)! }
let N = nm[0]
let M = nm[1]

var stack = [Int]()

private func dfs() {
    if stack.count == M {
        print(stack.map{ String($0) }.joined(separator:" "))
        return
    }

    for i in 1...N {
        if !stack.contains(i) {
            stack.append(i)
            dfs()
            stack.removeLast()
        }

    }
}

dfs()