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

요구능력 : DFS의 응용

 

코드설명 : 

 

DFS를 활용하는 백트래킹 문제이다.

 

백트래킹이란?

탐색하는데 필요한 많은 자원을 줄이기 위해 유망성있는 노드들을 중심으로 탐색하는 방법이다.

조건을 줘서 필요없는(유망성없는) 노드에는 방문조차 하지않는다.

백트래킹이라는 방법을 사용하기위해 DFS를 이용한다고 생각하면 된다.

 

이 문제에서 핵심 두 가지다.

1. 수열을 만들되, 백트래킹을 이용하여 중복되는 수(유망성없는 수)를 방문하지 않는다는것이다.

2. DFS를 사용하기 때문에 Stack을 활용한다는 것이다.

 

문제예시)

4 4를 입력했다고 치자.

아래 코드를 실행하게 되면,

result(0)

depth = 0, visitied[1] = false -> visited[1] = true, stack = [1]

result(1) 

depth = 1, visitied[1] = true니까 다시 for문 -> visited[2] = false -> visited[2] = true, stack = [1, 2]

result(2)

depth = 2, visitied[1]과 visited[2] = true니까 다시 for문 -> visited[3] = false -> visited[3] = true, stack = [1, 2, 3]

result(3)

depth = 3, visited[1]과 visited[2]와 visited[3]은 true니까 다시 for문 -> visited[4] = false -> visited[4] = true, stack = [1, 2, 3, 4]

result(4)

depth = 4, if문에 걸려서 print하고 리턴

 

그럼 result(3)에서 i는 4인 상태에서 result(4)를 실행했기 때문에, visited[4] = false가 되고 stack = [1, 2, 3] 이 된다.

이제, result(3)은 모든 일을 끝마쳤으니 리턴이나 마찬가지고 남은 함수스택은 result(2)와 result(1)과 result(0)이다.

 

result(2)에서 i는 3인 상태에서 reuslt(3)을 실행했기 때문에, visited[3] = false, stack = [1, 2]가 된다.

그리고 i = 4일 때, visited[4] = true고 stack = [1, 2, 4]가 되게 된다.

그렇게 result(3)이 시작되고 for문에서 유망하지 않은노드(이미 방문해서 또 방문하면 중복이 되는노드)를 if문으로 거르고

visited[3] = true, stack = [1, 2, 4, 3]이 되게된다.

 

후기 : 

브루트포스로 열심히 풀다가 도저히 아닌거 같아서 찾아봤는데, DFS로 백트래킹을 하는거였다..

전에 DFS개념은 공부한적이 있어서 이해하는데 큰 어려움이 있었던것은 아니었지만, 처음보는 유형이라 애매했다.

이렇게 스택과 백트래킹을 이용해서 문제를 풀어보았는데 코드는 간단한거 같지만 들어가는 개념이 은근있어서 중요한 유형이다.

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

var visited = Array(repeating: false, count: n + 1)
var depth: Int = 0

var stack: [Int] = []

func result(depth: Int) {
    if depth == m {
        print(stack.map{String($0)}.joined(separator: " "))
        return
    }else {
        for i in 1...n {
            if !visited[i]{
                visited[i] = true
                stack.append(i)
                result(depth: depth + 1)
                visited[i] = false
                stack.removeLast()

            }
        }
    }

}

result(depth: depth)