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

🟠 문제

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

15650번: N과 M (2)

🟠 내가 푼 풀이

앞서 풀었던 N과 M(1) 과 비슷하다. [1,2]와 [2,1]을 다르게 취급햇던 (1)번 문제와는 달리 (2)번 문제는 [1,2] 하나만, 즉 오름차순으로 이루어진 답 하나만 취급해야한다. 

어제 DFS관련해서 헤맸던게 나름 충격이었어서 머릿속에 몇번이고 기억하면서 넣었었다. 그래서 코드는 쉽게 짤 수 있었다. 이제 오름차순으로 이루어진 것들만 뽑아내는 것인데,,, 내가 생각한 방식은 두 가지가 있었다. (결국 두가지모두 틀렸지만)

🔖 stack에 쌓이는 것들을 오름차순정렬한 후, Set으로 중복처리를 해주자.

이렇게 해도 답이 나오긴 할 거다. (1)번과 같은 풀이방식으로 풀어서, stack을 바로바로 print하지 않고, stack에 모두 쌓아두었다가, 나중에 출력하기 전에 정렬 및 중복처리를 해주는 방식이다. 정말, 바보같지만 1차원적으로 가장 먼저 생각할 수 있는 방법이었다.

하지만, DFS로 풀어보고 싶은 마음이 컸다. 이렇게 풀면 100%풀릴것이라고 확신이 들었고, 시간제한도 충분해서 풀 수 있었지만 이렇게 푸는 방식은 나도 원하지 않았기 때문에 방법으로만 생각해두고 다른 풀이를 생각했다.

🔖 visited를 만들어서 방문처리를 해주자..

이 방식은 생각하다가 풀리지 않아서 버렸다. 왜냐면, 1부터 반복해서 1번에 visited 처리, 2번에 visirted처리,, 순서대로 가면, 오름차순이지만 만약 2부터 돈다치면, 1에 방문해서 방문처리 안되어있으면 visited처리해주고 stack에넣고.. 결국 (1)번문제와 같다는 것이다... 하하하하 결국 같군.. 

기존 (1)번 풀이를 보면, contains 메서드를 통해서 stack에 들어있는지의 여부를 판단한다. 이게 바로 visited 처리와 비슷한 기능을 하기 때문에 내가 굳이 visited 를 만든다 쳐도,, 별다른 풀이가 아니라는 것이다.

 

✅ dfs에 넘겨주는 값을, 지금 넘겨주는 값보다 큰값만 취급해보자.

결국, 인터넷에서 조금의 힌트를 얻었다. 여기서 얻은 힌트는, 오름차순으로 되어있는 것들만 취급해야하기 때문에, 3부터 시작했으면 굳이 1과 2는 살펴보지 않아도 된다는 것이다. 즉, dfs를 재귀로 넘겨주는 과정에서 현재의 값보다 큰 값들만 취급하게 되면? 오름차순으로 이루어진 것들만 자연스럽게 출력될 것이다!! 

 

🟠 정답코드

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

var stack = [Int]()

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

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

dfs(start: 1)