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

저도 백트래킹은 처음이라 백트래킹의 개념에 대해 먼저 짚어보면 다음과 같습니다.

백트래킹의 핵심

1. DFS(깊이 우선 탐색)를 기반으로 합니다.
2. 탐색 중, 조건에 맞지 않는 경우를 가지치기(pruning)하여 탐색 범위를 줄입니다.
3. 탐색이 끝난 후, 상태를 이전으로 복원(backtracking)합니다.

풀이 아이디어는 다음과 같습니다.

1. DFS를 이용해 깊이 우선으로 탐색:
   • M 길이에 도달할 때까지 가능한 숫자를 하나씩 추가.
2. 가지치기:
   • 이미 선택한 숫자는 다시 선택하지 않음.
3. 상태 복원:
   • 재귀 호출 후, 선택했던 숫자를 제거하고 이전 상태로 되돌아감.

풀이 코드는 아래와 같습니다.

풀이

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

var resultArr = [Int]() // 현재까지 선택된 숫자를 저장하는 배열

func dfs() {
    if resultArr.count == m {
        // 조건을 만족하면 결과 출력
        print(resultArr.map { String($0) }.joined(separator: " "))
        return
    }

    for i in 1...n {
        if !resultArr.contains(i) { // 중복 방지
            resultArr.append(i) // 숫자를 추가
            dfs()              // 다음 단계로 탐색
            resultArr.removeLast() // 상태 복원
        }
    }
}

dfs() // 탐색 시작

보통 재귀를 통해 풀이하는거 같더라고요
하지만 저는 재귀가 유독 가독성이 떨어진다고 생각해서 아래는 배열을 통해 풀이해보았습니다.

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

var queue: [(current: [Int], depth: Int)] = []
queue.append(([], 0))

while !queue.isEmpty {
    let (current, depth) = queue.removeFirst()

    if depth == m {
        print(current.map { String($0) }.joined(separator: " "))
        continue
    }

    for i in 1...n {
        if !current.contains(i) {
            queue.append((current + [i], depth + 1))
        }
    }
}

보통 dfs에선 stack을 사용하는게 일반적이라 removeLast를 사용하겠지만, 임의로 변경해봤습니다.(for문에서 reversed를 쓰고싶지 않았음)
정석적인 풀이는 아니지만 이런 방식으로도 풀 수 있습니다!