[C/C++] 백준 15649번 N과 M (1) - 참고

 

 

 

 

코드

 

#include <iostream>

using namespace std;

int N, M;
int num[9];  // N,M 범위 1<=N,M<=8
bool visited[9]; // 방문 표시 -> false: 미방문, true : 방문

void DFS(int n) {

	if (n == M) { // M까지 도달했을 경우
		for (int i = 0; i < M; i++) {
			cout << num[i] << " "; // M까지 저장된 num 값 출력
		}

		cout << "\n";
	}

	else {// M 도달 전
		for (int i = 1; i <= N; i++) { // 
			if (!visited[i]) { // 미방문
				visited[i] = true; // 방문 체크
				num[n] = i; // i 값을 num[n]에 저장
				DFS(n + 1); // M 까지 탐색
				visited[i] = false; // 백트래킹 설정
				// 현재 상태에서 다음상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다. 
				//여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 한다.
			}
		}
	}
}

int main()
{
	cin.tie(0); // 코드를 작성하면 입출력 속도가 빨라진다. -> C와 C++ 표준 stream의 동기화를 비활성화
	cout.tie(0); // C++의 입출력인 cin, cout만 사용하도록 주의해야합니다.

	cin >> N>>M;

	DFS(0); // 0부터 시작

	return 0;
}