[백준 15650] N과 M(2) - C++ / 백트래킹, 재귀 알고리즘

문제

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

15650번: N과 M (2)

나의 코드

저번시간에는 재귀를 통한 '순열 구현'을 배웠다면

이번시간에는 재귀를 통한 '조합 구현'이다.

** 참고 사이트 : https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

#include <iostream>
#define MAX 8
 
using namespace std;
 
int arr[MAX];
bool visited[MAX];
int cnt, idx, n, m;
 
void Print() {
    for (int i = 0; i < n; i++)
        if (visited[i]) {
            cout << arr[i] << " ";
        }
    cout << '\n';
}
 
void DFS(int cnt, int idx) {
    if (cnt == m) {
        Print();
        return;
    }
 
    for (int i = idx; i < n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
 
        DFS(cnt + 1, i + 1);
        visited[i] = false;
    }
}
 
int main(void) {
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
        visited[i] = false;
    }
 
    DFS(0, 0);
}

 

확실히 순열을 배우고 풀으닌깐 더 이해가 잘 되는 것 같다.

조합은 순열과 달리 중복되면 안되므로 idx(시작점)이 필요하다.

다음 cnt(count)로 넘어갈 때 이전에 건든 작은 숫자를 건들지 않도록 하기 위해 idx가 있는 것이다.

 

<입력>

4 2

 

<출력 결과>

1 2
1 3
1 4
2 3
2 4
3 4

 

<이해>
1. cnt = 0, idx = 0 , i = 0

visited = {1}  //앞으로 visited에는 true인 값을 표시한다(실제는 bool타입)

2. for문으로 들어가서 i = idx = 1부터 시작

cnt = 1, idx = 1, i = 1

visited = {1,2}

3. for문으로 들어가서 i = idx = 2부터 시작

cnt = 2, idx = 2, i =2

visited = {1,2,3}

4. cnt = 3 , 출력

 

5. DFS(cnt + 1, i + 1);로 돌아온다.

cnt = 2, idx = 2,  i = 2

visited[2] = false;

6. cnt = 2, i = 3 -> idx = 4(이때 idx는 중요하지 않는다)

visited = {1,2,4}

7. cnt = 3, 출력

 

8. DFS(cnt + 1, i + 1);로 돌아온다.

cnt = 2, idx = 2,  i = 3

visited[3] = false;

9. cnt = 2, i = 4 -> idx = 5

visited = {1,2,5}

10. cnt = 3, 출력

 

11. cnt = 2, idx = 2,  i = 4

   visited[4] = false;

   for문이 끝남!!!!!

 

12.  DFS(cnt + 1, i + 1);로 돌아온다.

    cnt = 1, idx = 1, i = 1

    visited[1] = false;

13. cnt = 1, i = 2

   visited = {1, 3}

   dfs(cnt = 2, idx = 3)  //문법상 맞지 않지만 이해를 위해 적음

14. for문으로 들어와서 i = idx = 3부터 시작

cnt = 2, idx = 3 , i =3

visited = {1,3,4}

 

 

그리고 1로 시작하는 수열이 끝나면

cnt = 0, idx = 0, i = 0 으로 돌아가서 

visited[0] = false;

 

cnt = 0, i = 1 

visited = {2}

dfs(cnt = 1, idx = 2)