[DFS] N과 M - baekjoon Swift

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

15649번: N과 M (1)

 

풀이방법

일단 이 코드의 순열과 조합을 만드는 이 메커니즘은 다음과 같습니다. [1,2,3] 배열에서 2개를 순서있게 뽑는 경우의 수를 예시로 들겠습니다.

1. 답이 들어갈 수 있는 두자리를 준비합니다. [ , ]
2. 첫번째 자리부터 보겠습니다. 첫번째 자리에 올 수 있는 가능성 있는 숫자는 1, 2, 3 입니다. 일단 첫번째 자리에 1을 고정 
3. 두번째 자리로 넘어갑니다. 이제 남은 숫자는 2, 3 입니다. 일단 두번째 자리에 2를 고정
4. 이제 result = [1,2] 로 2개가 찼으니 종료조건을 만족하므로 출력하고 종료합니다.
5. 두번째에서 숫자가  2, 3 있었죠? 2는 끝났으니 3으로 넘어가서 [1, 2] 에서 -> [1, 3] 으로 변경해 줍니다.

이런식 입니다. 요약해서 설명하자면 각각의 자리에 올 수 있는 가능성있는 숫자들을 전부 도는 것이죠.

백트래킹인 이유는 모든 수 1,2,3에서 계속 탐색하는게 아니라 올 수 있는 가능성있는 숫자들을 도는 것 이기 때문입니다.

 

코드

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

import Foundation

//DFS: 가능한 모든 경우의 수를 탐색하는 것
//백트래킹: 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것
//답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것
let input = readLine()!.split(separator: " ").map{Int(String($0))}
let n = input[0]!
let m = input[1]!
//1부터 n까지 들어있는 배열을 만든다.
let arr = Array(1...n)
var result = [String](repeating: String(), count: m)
var visited = [Bool](repeating: false, count: n)

//permutation 순열
func solution(depth: Int) {

    //종료조건
    if depth == m {
        print(result.joined(separator: " "))
        return
    }
 
    //m개의 수 뽑기
    for i in 0..<n {
        if visited[i] {
            continue
        } else {
            visited[i] = true
            result[depth] = String(arr[i])
            solution(depth: depth+1)
            visited[i] = false
        }
    }
}

//combination 조합
//func solution2(depth: Int) {
//
//    //종료조건
//    if depth == m {
//        print(result.joined(separator: " "))
//        return
//    }
//
//    //m개의 수 뽑기
//    for i in depth..<n {
//        if visited[i] {
//            continue
//        } else {
//            visited[i] = true
//            result[depth] = String(arr[i])
//            solution(depth: depth+1)
//            visited[i] = false
//        }
//    }
//}

//solution2(depth: 0)

위에 있는 메커니즘을 코드로 표현한 것인데 재귀라서 잘 모르겠죠.. 저도 생각 엄청 많이 했습니다.

원래 메서드는 메모리영역의 스택에 쌓인다는 건 알고 있었는데 이번에 재귀 동작 방식을 보다가 어? 이거 메서드인데 들어간 것이 먼저 나오네? 아 이래서 스택이구나 이렇게 다시한번 깨달을 수 있었습니다. 굿

일단 재귀쪽이 이해가 안가실텐데 보충 설명하겠습니다. (망)

 

solution(depth: 0)을 하면 

i == 0, depth == 0 - visitied = [true, false, false] - solution(depth: 0) 실행 - result = [1, ]

i == 1, depth == 1 - visitied = [true, true, false] - solution(depth: 1) 실행 - result = [1, 2] ,  visitied = [true, false, false]만듬

i == 1, depth == 2 - solution(depth: 2) 실행 출력하고 바로 종료

solution(depth: 0) 는 아직 안끝남 현재상황(i == 0)

solution(depth: 1) 도는중 (i == 1) 일 때 visitied = [true, false, false]만들고 다음 i == 2 로 넘어감

result = [1,3]을 만듬

solution(depth: 2) 실행 출력하고 종료

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 사실 글로보면 잘 모르겠죠.. 네 저도 브레이크포인트 걸어가면서 이해했습니다. 🤣

일단 메커니즘을 알아두고 브레이크 포인트 찍어서 하나씩 보시면 처음엔 이해가 안가겠지만 천천히 다시 생각해보면 아..하? 조금은 이해하기 됩니다.