[C++] 순열구하기(DFS : Depth First Search) 🔥

📄 문제

자연수 N과 R이 주어지면 서로 다른 N개의 자연수 중 R개를 뽑아 일렬로 나열하는 프로그램을 작성하세요.

 

⬇️ 입력

첫 번째 줄에 자연수 N(1<=N<=15)과 R(0<=R<=15)이 주어진다. 단 (N>=R)

두 번째 줄에 N개의 서로 다른 자연수가 오름차순으로 주어진다.

4 3 1 3 6 7

 

⬆️ 출력

순열의 각 경우를 아래와 같이 오름차순으로 출력한다. 마지막 줄에 총 개수도 출력한다.

1 3 6 1 3 7 1 6 3 1 6 7 1 7 3 1 7 6 3 1 6 3 1 7 3 6 1 3 6 7 3 7 1 3 7 6 6 1 3 6 1 7 6 3 1 6 3 7 6 7 1 6 7 3 7 1 3 7 1 6 7 3 1 7 3 6 7 6 1 7 6 3 24

 

📝 풀이

#include <iostream>

int N, R;
int arr[16];
bool ch[16];
int cnt = 0;
int res[16];

void DFS(int level)
{
	// 사용 개수가 R에 도달했다면?
	if (level == R)
	{
		++cnt;

		for (int i = 1; i <= R; ++i)
			printf("%d ", res[i]);

		printf("\n");
	}
	else
	{
		for (int i = 1; i <= N; ++i)
		{
			if (!ch[i])
			{
				// 출력 결과는 res[level + 1]에 담기
				res[level + 1] = arr[i];

				// ch[i]번째의 값을 현재 사용중
				ch[i] = true;

				// 개수는 1씩 증가
				DFS(level + 1);

				// ch[i]번째의 값을 현재 사용 해제
				ch[i] = false;
			}
		}
	}
}

int main()
{
	scanf_s("%d %d", &N, &R);

	for (int i = 1; i <= N; ++i)
	{
		scanf_s("%d", &arr[i]);
	}

	// 0번 인덱스로 시작
	DFS(0);

	printf("%d", cnt);
}

• DFS for문에서 1부터 N까지 반복하여 선택할 수 있는 값들을 선택하여 res값에 저장합니다.
• res 값은 level이 R에 도달했을경우, 해당 값들을 출력하기 위해 사용합니다.