[C] 백준 15650번 N과 M (2)

링크
https://www.acmicpc.net/problem/15650

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 3
2 4
3 4

예제 입력 3

4 4

예제 출력 3

1 2 3 4

아이디어 스케치

• 앞서 풀었던 N과 M (1) 문제를 조금 변형한 문제이다.
• 이 문제는 depth가 큰 가지는 작은 가지보다 값이 더 커야한다는 점이 앞서 풀었던 문제와 다르다.
• 위 조건을 만족하기 위해 DFS의 전달인자에 현재 바로 위 가지의 값을 확인할 수 있는 인자를 추가해야 한다.
• 중복이 없어야 한다는 것은 앞서 풀었던 N과M(1) 문제와 같다.
• https://velog.io/@dnddl9456/C-%EB%B0%B1%EC%A4%80-15649%EB%B2%88-N%EA%B3%BC-M-1

코드 분할 설명

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

• N과 M을 입력 받은 후 DFS(0,0)을 호출한다.

void DFS(int depth, int cut)
{
	int i;

	if (depth == M)
	{
		for (i = 0; i < M; i++) {
			printf("%d ", result[i]);
		}

		printf("\n");
	}
	else
	{
		for (i = 1; i <= N; i++)
		{
			if (check[i] == 0 && cut < i)	//앞서 푼 문제와 다르게 바로 위 가지의 값을 확인할 수 있는 cut 변수가 생김
			{
				result[depth] = i;
				check[i] = 1;
				DFS(depth + 1, i);		//현재 가지의 값을 다음 가지에 전달
				check[i] = 0;
			}
		}
	}
}

• 이 문제의 핵심 부분이다.
• 앞서 푼 문제와 다른 점은 현재 가지의 값을 다음 가지로 전달한다.
• 중복을 허용하지 않기 때문에 check배열을 사용하여 중복을 확인하고 바로 위 가지의 값보다 커야하기 때문에 전달받은 위 가지의 값보다 클 때만 가지를 뻗어나간다.
• 그 외에는 앞서 푼 문제와 같다.

전체 코드

#include <stdio.h>

int N, M;
int result[1000];
int check[1000];

void DFS(int depth, int cut)
{
	int i;

	if (depth == M)
	{
		for (i = 0; i < M; i++) {
			printf("%d ", result[i]);
		}

		printf("\n");
	}
	else
	{
		for (i = 1; i <= N; i++)
		{
			if (check[i] == 0 && cut < i)
			{
				result[depth] = i;
				check[i] = 1;
				DFS(depth + 1, i);
				check[i] = 0;
			}
		}
	}
}
int main(void)
{
	scanf("%d %d", &N, &M);
	DFS(0, 0);
	return 0;

}

제출 결과