[15649번] N과 M(1)

백트래킹 문제를 풀려고하면 구현력을 상당히 필요로하고 실수하기도 쉬운구간입니다.

또한 재귀의 특성상 한 번 오류가 나면 디버깅하는데 오래걸리기 때문에 그래서 많은 시간을 쌓아야 한다고 생각합니다.

위 알고리즘은 8중 for문을 쓰면 어거지로 풀 수는 있지만, 조금 있어보이게 (?) 풀기 위해서는 백트래킹 알고리즘을 사용해서 풀면 좋습니다.

비어있는 리스트에서 시작해서 수를 하나씩 추가하면서 길이가 M인 수열을 완성되면 출력하는 방식으로 구현할 수 있습니다. 하지만 이걸 구현한다고 하면 사실 감이 잘 안옵니다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10]; //수열을 담을 배열
bool isused[10]; //특정 수가 쓰였는지를 true 혹은 false로 나타내는 배열

void func(int k){ //현재 k개까지 수를 택했음
	if(k==m){ //m개를 모두 택했으면
    	for(int i = 0; i<m;i++)
        	cout << arr[i] << ' '; //arr에 기록해둔 수를 출력
        cout << '\n';
        return;
    }
    
    for(int i =1 ; i<=n; i++){ //1부터 n까지의 수에 대해
    	if(!isused[i]){//아직 i가 사용되지 않았으면
        	arr[k] = i; //k번째 수를 i로 정함
            isused[i] = 1; //i를 사용되었다고 표시
            func(k+1); //다음 수를 정하러 한 단계 더 들어감
            isused[i] = 0; //k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용하지 않았다고 명시
        }
    }
}

int main(void){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0);
}

여기서 func이 재귀 함수이니 당연히 base condition이 필요하고, k=m이 되었을 때, m개를 모두 택했으니 수열을 출력한 함수를 종료하면 된다는 것을 알 수 있습니다.

k가 m이 아니라면 if문을 건너뛰어 15번째 줄로 넘어오고 여기서부터는 1부터 n까지 수를 차례로 확인하면 아직 쓰이지 않은 수를 찾아내게 됩니다. !isused[i]에서 isused[i]가 false일 때 if 문이 참이 되고 arr[k] = i, isused[i] = true 로 만든 후

func(k+1)을 호출하게 됩니다. 그 이후 20번째 줄에 도착했다는 것은 arr[k] = i로 둔 상태에서 func(k+1)에 들어갔다가 모든 과정을 끝냈다는 이야기이므로 isused[i] = 0으로 만들어 i가 사용되지 않고 있음을 명시해야합니다.

단, 현재 값이 i인 arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없는데 어차피 자연스럽게 다른 값으로 덮힐 예정이라 그런것입니다.