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

문제

 

---

풀이

 

백트래킹의 기본 문제이다. 백트래킹은 해당 value의 방문 여부를 따지며 주로 재귀함수로 구현하는 경우가 많다. 그렇기 때문에 전역 변수 쓸 일이 좀 많다. 백트래킹 문제를 그림으로 표현할 때 트리를 많이 사용하는데 이 문제도 간단히 트리로 나타내면

이런 모습이다. visited를 true로 하느냐 false로 하느냐에 따라 트리의 아래로 가거나 위로 올라갈 수 있다.

 

이 문제도 노드들을 방문하며 visited를 갱신하고, 배열에 값을 넣는다. 배열의 크기가 M이 되면 트리 탐색을 끝내고 배열에 있는 수를 출력한다. 재귀함수는 아무래도 머리로 따라가기가 좀 까다로우니 그림을 그려가며 공부하면 좋을 것이다.

---

소스코드

 

#include <iostream>
using namespace std;
const int MAX = 8;

int N, M;
int arr[MAX];
bool visited[MAX] = { 0, }; //false로 초기화

void backNM(int cnt) {
	if (cnt == M) { //배열 끝까지 완성하면 출력
		for (int i = 0; i < M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
	}
	else {
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				arr[cnt] = i + 1;
				visited[i] = true; //방문 표시
				backNM(cnt + 1); //가지 아래로 내려감
				visited[i] = false; //위로 다시 올라감
			}
		}
	}
}

int main() {
	cin >> N >> M;
	backNM(0);
}