[백준] (Swift) N과 M (2)

15650번: N과 M (2)

 

📌 풀이

중복되지 않아야 하는 수열이므로 조합을 구현하는 문제이다. 그렇다면 조합을 어떻게 구현할까? 바로 백트래킹 알고리즘으로 구현하면 된다.

백트래킹(Backtracking) - DFS로 구현

1. 배열 2개를 만든다.

• 백트래킹의 진행 과정에 대한 배열 `sequence`
• 노드의 방문 여부에 대한 배열 `visited`

2. DFS 함수를 정의하여, Base Case와 Recursive Steps에 대한 알고리즘을 세운다.

• Base Case: 깊이의 끝에 도달했을 때 여태 쌓인 진행 과정을 원하는 형식으로 변환하여 출력
• Recursive Steps: `N`만큼 반복하되, 방문하지 않은 노드이면 방문 처리를 하고 다음 노드에 대한 재귀함수를 호출한다. (조건문에 도달하지 않았으면 이 길이 아니므로) 이후 다시 방문 처리를 철회하고, 가장 진행 과정의 마지막 요소를 제거한다.
• 예외 조건 추가: 오름차순 조건을 위해 마지막에 진행 과정에 대한 배열에서 배열이 비어 있거나 삽입한 숫자보다 큰 숫자여야 한다는 조건을 추가한다.

 

📌 코드

import Foundation

// 첫째 줄 입력
let input = readLine()!.split(separator: " ").map { Int($0)! }

// N과 M 할당
let N = input[0]
let M = input[1]

// dfs에 활용할 배열 2개(진행 과정, 방문 여부) 초기화
var sequence = [Int]()
var visited = [Bool](repeating: false, count: N)

// dfs 함수 실행
dfs(0)

// dfs 함수 정의
func dfs(_ depth: Int) {
    if depth == M {
        print(sequence.map { String($0) }.joined(separator: " "))
        return
    }
    for i in 0..<N {
        if !visited[i] && (sequence.isEmpty || sequence.last! <= i) {
            visited[i] = true
            sequence.append(i + 1)
            dfs(depth + 1)
            visited[i] = false
            sequence.removeLast()
        }
    }
}