[알고리즘/문제풀이/BOJ 15649번] N과 M (1)

15649번은 백트래킹 기법으로 해결할 수 있는 문제입니다. 백트래킹은 모든 경우를 탐색하는 기법으로 보통 재귀함수를 이용하여 구현합니다. 재귀함수로 구현할 때는 함수 내에서 동일한 함수를 활용하여 부분 문제를 풀 수 있도록 작성하여야 합니다. 공통적으로 재귀함수는 탈출조건과 호출부로 나누어지게 됩니다. 해당 문제에서는 탈출조건은 depth가 M일 때이며 이때 탐색한 수열을 출력하고 재귀함수를 종료하게 됩니다.

작성한 코드는 다음과 같습니다.

#include<stdio.h>

int N, M;

int sequence[10];
int check[10];

//back tracking은 모든 경우를 탐색할 때 사용하는 기법입니다.
//기능 특성상 재귀함수 형태로 구현됩니다.

void final_process() {
	for (int i = 0; i < M-1; i++) {
		printf("%d ", sequence[i]);
	}
	printf("%d\n", sequence[M - 1]);
}

void back(int depth) {

	if (depth == M) {
		final_process();
		return;
	}
	else {
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) {
				sequence[depth] = i;
				check[i] = 1;
				back(depth + 1);
				check[i] = 0;
			}
			else if (check[i] == 1) {
				continue;
			}
		}
	}

	return;
}

int main(void) {

	scanf("%d %d", &N, &M);

	back(0);
}

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