[백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹)

[백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹)

N과 M 시리즈는 엄청 많아서 1을 통해 dfs랑 백트래킹을 익히는 것에 초점을 뒀다.

그리고 해당 코드를 암기해서 다른 것들에 응용하는게 수월할 것 같다.

 

코드

#include <iostream>

using namespace std;

int n, m; 
int arr[9];
int arred[9];

void dfs(int idx){
    if(idx == m){
        for(int i=0; i<m;i++){
            cout << arr[i] <<' ';
        }
        cout << "\n";
        return ;
    }
    
    for(int i=1; i<=n; i++){
      if(arred[i]==0){
          arr[idx] =i;
          arred[i] =1;
          dfs(idx+1);
          arred[i]=0;
      }
    }
}

int main (){
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);

    cin >>n>>m;
    dfs(0);

    return 0;
}

 

상세 설명

처음에 코드만 봤을 때는 정말 어떤 로직을 이용하는 것인지 알 수 없었다.

알고 있는 정보는 DFS를 이용해서 갔다 온 구역은 표시를 해주는 것이다.

최대한 DFS 의 개념을 이용해서 코드를 이해해보고자 했다

 

idx => 깊이 

깊이 증가될 때 조건문에 의해서 m이랑 같으면 출력

 

4 2를 넣었을 때 

1. arr[0] = 1 arred[1] = 1 // 1을 써서 표시함

1) arr[1] = 2 arred[2] = 1 // 2도 사용 -> dfs(2) -> if문 실행 > arred[2] =0;

2)(idx ==1 인 상태) arred[3] ==0 -> arr[1] =3 arred[3] =1; -> dfs(2) -> if문 실행 -> arred[3] =0;

3)(idx ==1 인 상태) arred[4] ==0 -> arr[1] =4 arred[4] =1; -> dfs(2) -> if문 실행 -> arred[4] =0;

 

2. (idx==0 으로 복귀) arred[1] ==1 -> arred[2] ==0 arr[0] = 2  arred[2] =1 -> dfs 끝 -> arred[1] =0;

1) (idx ==1) arr[1] = 1 -> arred[1] =1 -> dfs(2) ...

(반복)

 

정리

1) arr[0] = 1
2) arred[1] = 1 //1사용
3) dfs(1)로 이동
4) dfs(1)에서 for문 1 사용했으니 스킵하고 arr[1]=2
5) arred[2] = 1 //2사용
6) dfs(2)로 이동
7) idx 2라서 출력하고 함수 탈출
8) arred[2] = 0 // 2미사용
9) arr[1] = 3
10) arred[3] = 1
11) dfs(2)로 이동...

 

dfs 백트래킹 너무 어렵다 .. !!