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

백준 온라인 저지(BOJ) 15649번 N과 M (1)

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

15649번: N과 M (1)

* 사용언어 : C언어, C++

 

1. 문제

N개의 수에서 M개의 숫자를 중복없이 뽑아 나열하는 모든 경우를 출력 (nPm 순열)

 

2. 풀이

DFS 방식으로 재귀 함수를 구현하여 순열을 출력하도록 구현하였습니다.

순열 출력을 위해 선언한 배열은 총 2개로 ① 출력할 순열을 저장하는 arr, ② 숫자의 사용 여부를 저장하는 visited 입니다.

 

문제에서 주어지는 N과 M의 최대값은 8이지만

직관적인 구현을 위해 visited 배열은 크기를 9로 선언했습니다. (i를 1부터 8까지 사용)

 

그 외 내용은 일반적인 DFS 알고리즘과 같으니 아래 코드로 설명 대체하겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
15649_N과 M (1)
1112KB	24ms
*/
#include <cstdio>

const int LM = 8;
int arr[LM], visited[LM + 1], N, M;

void permutation(int idx) {
	if (idx == M) {
		for (int i = 0; i < M; ++i) printf("%d ", arr[i]);
		printf("\n");
		return;
	}

	for (int i = 1; i <= N; ++i) {
		if (visited[i]) continue;
		visited[i] = 1;
		arr[idx] = i;
		permutation(idx + 1);
		visited[i] = 0;
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &M);
	permutation(0);
	return 0;
}