[C++] 백준 알고리즘 15649 N과 M (1) (백트래킹)

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

백트래킹이란?

브루트 포스와 같이 완전 탐색을 하는 알고리즘이 있는데, 여기서 조건에 해당되지 않는 경우를 가지치기 하여 경우의 수를 줄여나가는 방법을 백트래킹이라고 한다. 백트래킹을 이용하면 탐색 시간이 줄어든다.

 

백트래킹에서는 주로 재귀함수를 이용한다. 이때, 재귀함수의 종료조건이 중요하다.

백트래킹은 주로 N의 값이 20보다 작을 때 이용한다.

 

위 N과 M (1)의 문제를 예로 들어보자.

n=4, m=2로 주어지면 1~4까지 수 중 2개의 수를 골라 나열하면 된다. 단 2개의 수는 중복되지 않고, 2개의 수는 순서를 지켜야한다. 출력 시 2 1과 1 2는 다른 경우라고 인식한다.

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

 

총 12가지 경우의 수가 나온다.

백트래킹을 사용해보자.

 

1. 수열을 담을 배열 = num이 있다.

위의 경우에서 첫 번째로, num[0]에는 1, num[1]에는 2가 온다.

그리고 종료조건 (m=2, 즉 길이가 2)를 만나면 num 값이 바뀐다.

num[1]값이 3으로 바뀌게 되는 것이다. 이런식으로 12 줄을 출력하게 된다.

 

2. check배열이 있다.

이 배열은 중복을 방지하는 것인데,

1 1이 나오면 안되므로, 내가 방문한 배열을 true로 바꿔준다.

check[1] = true로 변경하면 1은 방문했다는 의미이니 다시 방문하지않고,

즉 1 1을 건너뛰고 1 2 를 출력하게 된다.

이때!

1 2, 1 3, 1 4를 출력하고 다시 1을 false로 바꿔줘야한다.

왜냐하면 뒤에서 2 1, 3 1, 4 1를 출력해야하는데 1이 true로 되어있다면 출력할 수 없기 때문이다.

 

이 문제를 통해 백트래킹을 정리하자면

1. 종료 조건을 잘 설정하자

2. 입력 범위가 작을 때 (N<20) 사용하자

3. 재귀함수를 사용하자

3. 원래 상태로 돌려주는 것을 잊지 말자

정도가 된다.

 

#include<iostream>

using namespace std;

const int SIZE=8;
int num[SIZE];
int check[SIZE+1]; //방문한 수 인지 체크하는 배열
int n,m;

void backtracking(int index){ //index = 수열의 index
    //종료조건
    if(index==m) {
        for (int i = 0; i < index; i++)
            cout << num[i] << ' ';
        cout<<'\n';
        return;
    }
    //백트래킹
    for(int i=1; i<=n; i++){
        if(!check[i]) { //중복되는 수가 없어야 하므로 check 배열 확인
            num[index]=i; //수열에 값 저장
            check[i]=true; // 방문 확인
            backtracking(index+1); //다음 수 검사
            check[i]=false; //원래대로 돌려놓기
        }
    }
}

int main() {
    cin>>n>>m;

    backtracking(0);
}