[백준] 15649번: N과 M(1)

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

15649번: N과 M (1)

백트랙킹 알고리즘을 사용하면 된다고 한다.

백트랙킹 알고리즘은 가능한 Decision Space를 검토하면서 불가능한 상황들을 제거해 나가는 방식이다. 

잘 이해는 안되고, 보통은 recursive한 문제풀이를 이용한다고 한다. 

 

작성 코드

#include <iostream>

using namespace std;

int N, M;
int visited[9];
int ans[9];

void Check(int cnt){
    if(cnt == M){
        for(int i = 0; i<M; i++){
            cout << ans[i] << " ";
        }
        printf("\n");
        return;
    }
    else{
        for(int i = 1; i<=N; i++){
            if(!visited[i]){
                visited[i] = 1;
                ans[cnt] = i;
                Check(cnt+1);
                visited[i] = 0;
            }
        }
    }
}

int main(void){

    cin >> N >> M;
    Check(0);

    return 0;
}

이미 들어간 숫자인지 확인하기 위해 배열 visited가 존재하고, 만든 수열을 저장하기 위한 ans가 존재한다.

Check함수를 재귀적으로 이용하면서 답을 찾아 나간다. 

 

예를 들어 M=3 일 때, 

cnt == 0 일 때, 1을 visit 하고 해당 숫자를 ans에 넣는다.

cnt를 하나 추가해서 Check(1)을 호출한다.

 

Check(1)에서는 두 번째 숫자를 고른다. 이때 visited를 참고하여 이미 수열에 넣은 숫자인지를 확인한다. 1은 visit된 상태이므로 2를 골랐다고 치자. 이 상태에서 세 번째 숫자를 고르기 위해 또 다시 Check(2)을 부른다.

 

Check(2)에서 마지막 숫자를 고른다. 3을 골랐다고 치고 Check(3)을 부르면, 이땐 cnt == M 이므로 ans에 저장된 수열(1, 2, 3)을 프린트한다. 그리고 Check(3)은 Check(2)로 리턴된다. 리턴되어 돌아온 Check(2)에서는 기존에 방문했던 3을 visited에서 지우고 루프 위로 돌아가서 다시 세 번째 숫자를 고른다.

 

이 과정이 반복되면 모든 가능성을 확인할 수 있다. 

 

계속 비슷한 유형의 문제를 풀어서 익숙해져야겠다.