백준 15655 N과 M (6) - Swift

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

15655번: N과 M (6)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 

3 1
4 5 2

예제 출력 1 

2
4
5

 

예제 입력 2 

4 2
9 8 7 1

예제 출력 2 

1 7
1 8
1 9
7 8
7 9
8 9

 

풀이  방법

2가지 방법으로 풀 수 있다고 생각합니다.

1번째 방법 - DFS

 

2번째 방법 - 백트래킹

1번째 방법을 이용하면 이 노드를 탐색했었는지 확인 할 필요가 없기 때문에 2번째 보다 좋다고 생각합니다.

왜냐하면 1번째는 탐색해야 할 노드만 존재하기 때문입니다.

그럼 어떻게 1번째 그래프를 DFS로 탐색할 지 재귀적으로 코드를 짜봅시다.

 

let NM = readLine()!.split(separator: " ").map{ Int(String($0))! }
var numbers = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted()
var answer = [Int](repeating: 0, count: NM[1])
var visited = [Bool](repeating: false, count: NM[0])
var str = ""

func dfs(start: Int, depth: Int) {
    if depth == NM[1] {
        str += answer.map{ String($0) }.joined(separator: " ")
        str += "\n"
        return
    }
    
    // 같은 depth의 노드를 옆으로 생성, 탐색하기 위한 for문
    for i in start..<numbers.count {
        answer[depth] = numbers[i]
        // depth + 1 을 해주어 깊이있게 탐색하기 위한 코드, start + 1 은 자신보다 큰 노드만을 탐색하기 위함
        dfs(start: i + 1, depth: depth + 1)
    }
}

dfs(start: 0, depth: 0)
print(str)

 

코드