[코테오답] BOJ 15649번 N과 M

Link : https://www.acmicpc.net/problem/15649

Level : S3

유형 : 백트래킹

---

📌 문제 탐색

순열 문제이다.

1부터 N까지의 자연수 중에서 중복없이 M개를 고른 수열을 출력하는 문제이다.

 

📌  코드 설계하기

1. n과 m을 입력 받는다.

2. 1부터 n까지 자연수가 존재하므로 반복문 for문을 돌며 모든 경우 탐색을 시작한다.

3. 재귀를 호출하여 현재 상태에서 가지치기를 하면서 모든 경우를 탐색한다.

- 그러다 cnt가 m이 되는 순간 현재까지 ans에 저장된 수를 출력하는 printNum이라는 함수를 호출하고 solve 함수를 종료한다.

- solve 함수가 종료되면, 방문 배열 visited와 정답 벡터 ans가 원래 이전 상태로 돌아가도록

- 해당 숫자의 visited를 0으로 바꾸고, 정답 벡터인 ans 벡터의 마지막 원소값을 빼내기 위해 pop을 한다.

4. 재귀가 호출되는 곳에 복원에 대한 코드가 작성되어 있어 첫번째 배치된 숫자는 사라지지 않았으므로, main 반복문에서도 solve 함수 아래에 상태 복원 관련 코드를 작성한다.

📌 정답 코드

#include <iostream>
#include <vector>
using namespace std;

int n, m, visited[10];
vector<int> ans;


void printNum(){
    for(int i: ans){
        cout << i << " ";
    }
    cout << "\n";
}


void solve(int cur, int cnt){
    visited[cur]=1;
    ans.push_back(cur);

    if(cnt == m){
        printNum();
        return;
    }

    for(int i=1; i<=n; i++){
        if(visited[i] != 1){
            solve(i, cnt+1);
            visited[i]=0;
            ans.pop_back();
        }
    
    }
    //visited[cur]=0;
    //ans.pop_back();
    //cnt-=1;
    
}

int main(){

    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        solve(i, 1);
        //memset(visited, 0, sizeof(visited));
        visited[i]=0;
        ans.pop_back();
    }

    return 0;
}

 

📌 오답노트

1. solve 함수의 배치될 숫자에 대한 매개변수를 n으로 지정한 것이 문제였다. 

 

(수정 전 🔨)

void solve(int n, int cnt)

 

(수정 후 💡)

void solve(int cur, int cnt)

 

solve 함수내에 있는 재귀를 호출하는 반복문이 아래와 같이 되어있는데, 여기서 n은 전역 변수의 n을 의도하고 작성한 것이다. 

하지만 solve의 매개변수 값을 n으로 설정하는 바람에 아래 반복문의 n이 매개변수 n으로 인식되어 원하는 로직으로 동작하지 못했다.

이 부분을 잘 챙겨야겠다.

for(int i=1; i<=n; i++){
        if(visited[i] != 1){
            solve(i, cnt+1);
            visited[i]=0;
            ans.pop_back();
        }
    
}

 

 

2. solve 함수 내 재귀를 호출하기 위한 반복문에서 재귀함수의 매개변수 중 cnt 부분을 cnt+1, cnt++, ++cnt를 설정하는 것에 따라 값이 다르다.

 

( 정답 💡)

for(int i=1; i<=n; i++){
        if(visited[i] != 1){
            solve(i, cnt+1);
            visited[i]=0;
            ans.pop_back();
        }
    
}

/*
4 2
1 2 
1 3 
1 4 
2 1 
2 3 
2 4 
3 1 
3 2 
3 4 
4 1 
4 2 
4 3 */

 

( 오답 -1 🔨)

for(int i=1; i<=n; i++){
        if(visited[i] != 1){
            solve(i, cnt++);
            visited[i]=0;
            ans.pop_back();
        }
    
}

/*
4 2
1 2 4 
1 3 
2 1 4 
2 3 
3 1 4 
3 2 
4 1 3 
4 2 
*/

 

( 오답 -2 🔨)

for(int i=1; i<=n; i++){
        if(visited[i] != 1){
            solve(i, ++cnt);
            visited[i]=0;
            ans.pop_back();
        }
    
}
/*
4 2
1 2 
2 1 
3 1 
4 1 
*/

 

재귀 호출 내부에서 cnt를 직접 증가시키면, 재귀 호출 이후에 원래 값을 복원하지 않아 문제가 생기는 것이다.

예를 들어, cnt가 1이고 solve(i, ++cnt)를 호출할 때:

1. cnt는 2가 된다.
2. 재귀가 끝난 뒤에도 cnt는 2로 유지된다.
3. 다음 숫자를 선택하려고 반복문으로 돌아오면, cnt가 이미 증가된 상태(2)로 남아 있어서 잘못된 결과를 낸다.

 

• 재귀 호출 이후 cnt의 값이 복구되지 않았다.
• 재귀 호출 간에 cnt의 상태가 공유되면서 논리가 꼬였다.

 

---

cnt++ 혹은 ++cnt를 하고 싶은 경우 함수의 매개변수가 아닌 외부에서 작성하고 solve에 그 cnt를 넣어주는 것은 가능하다.

아래의 3가지 코드는 모두 정답이다.

for(int i=1; i<=n; i++){
    if(visited[i] != 1){
        solve(i, cnt+1);
        visited[i]=0;
        ans.pop_back();
    }
    
}

cnt++;
for(int i=1; i<=n; i++){
    if(visited[i] != 1){
        solve(i, cnt);
        visited[i]=0;
        ans.pop_back();
    }
    
}

++cnt;
for(int i=1; i<=n; i++){
    if(visited[i] != 1){
        solve(i, cnt);
        visited[i]=0;
        ans.pop_back();
    }
    
}

 

 

• 반복문 바깥에서 cnt의 초기 상태를 유지하고, 반복문 안에서만 cnt를 증가시킨다.
• 이 방식에서는 cnt의 상태가 각 반복에서 독립적으로 처리되므로, 재귀 호출이 진행되는 동안 cnt 값이 혼란스러워지지 않는다.
• 따라서 재귀 호출이 끝난 뒤에도 cnt가 올바른 상태로 유지된다.

 

백트래킹은 재귀를 통해 상태를 탐색할 때, 현재 상태를 탐색한 뒤에는 원래 상태로 복원해야 한다.

복원을 정확한 위치에서 하지 않으면 상태가 꼬여 잘못된 값이 출력된다. ⭐⭐⭐