[백준]15649번 N과 M(1) c/c++

baaaarking dog 님 알고리즘강의 백트래킹파트를 참고하여 작성한 글입니다.

 

문제

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

15649번: N과 M (1)

 

설명

 

백트래킹이란??

현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.

가지치기처럼 그러셔 모든 경우의 수를 따라 그려볼 수 있다 (상태공간트리 라고도 불린다)

 

 

arr는 m개 만큼 원소를 담을 배열

isused는 1~N까지의 숫자가 사용되었는지 안되었는지 확인하는 배열

사용 - True  / 미사용 - False

 

여기서 조심해야할점은 사진상으로 왼쪽에 있는 1,2,3 이 다 채워졌기 때문에 즉 k=m이 만족해서

isused[3] =F 로 3을 미사용처리를 해줘서 1,2 만 채워져있는 칸으로 (위로) 올라가야한다.

 

 

코드

 

#include<iostream>
using namespace std;

int n, m;
int arr[10];
int isused[10];
void func(int k)
{
	if (k == m) {
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (isused[i] == 0) {
			arr[k] = i;
			isused[i] = 1;
			func(k + 1);
			isused[i] = 0;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	func(0);
}

 

 

코드상으로 처음부분만 설명하자면 (재귀이기때문에 귀납적방법으로 생각!!! 안그러면 헷갈림....)

main함수에서 func(0)을 호출해서

k=0이 들어갔을때

아직 1은 사용하지 않았으므로 isused[1] ==0이 만족하고 

arr[1]=1, isused[1] = 1을 남기고 func(1)을 호출한다...

 k = m이 되었을 때 m개를 모두 택했으니 수열을 출력한 후 함수를 종료하면 된다는 것을 알 수 있다.

만약 k가 m이 아니라면 if문을 건너뛰어 15번째 줄로 넘어오고 여기서는 1부터 n까지 수를 차례로 확인하며 아직 쓰이지 않은 수를 찾아낸다.

isused[i]=0에 도달했다는것은

arr[k] = i로 둔 상태에서 func(k+1)에 들어갔다가 모든 과정을 끝냈다는 얘기이므로

isused[i]=0으로 되돌려서 i가 사용되지 않고있음을 나타낸다.