링크
https://www.acmicpc.net/problem/15649
문제
자연수 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 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3예제 입력 3
4 4예제 출력 3
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1아이디어 스케치
- 백트래킹 알고리즘을 사용하는 문제이다.
- M개 만큼의 depth를 설정하여 나뭇가지 형식으로 뻗어나가야 한다. 첫번째 가지가 1일때 나올 수 있는 경우의 수를 재귀함수를 통해 전부 탐색하는데 이때 조건을 설정하여 가지치기를 해야한다. 이 문제에서는 중복되는 수열을 체크하여 중복될 경우 가지치기를 하면 된다.
- 벌써부터 어지럽다
코드 분할 설명
scanf("%d %d", &N, &M);
DFS(0);- N과 M을 입력받은 후 DFS함수에 전달인자를 0으로 하여 함수를 호출한다.
void DFS(int depth)
{
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)
{
result[depth] = i;
check[i] = 1; //check[i]를 1로 함으로써 중복이 안되게 설정
DFS(depth + 1);
check[i] = 0;
}
}
}
}- 이 문제의 핵심 알고리즘이다.
- N개중 M개를 고른 수열을 출력해야 하기 때문에 depth가 M이 될 경우 출력하고 이 함수를 호출한 부분으로 되돌아간다.
- for (i = 1; i <= N; i++)이 루프문을 통해 나올 수 있는 수열의 모든 경우의 수를 탐색한다.
- check는 수열의 중복을 체크하기 위해 사용한다. 일종의 가지치기이다. check는 현재 선택된 숫자를 1로 설정해놓고 1일 경우에는 생략하고 다음으로 넘어간다.(check[i]==0일 때만 가지를 뻗어나감)
전체 코드
#include <stdio.h>
int N, M;
int result[1000];
int check[1000]; //중복 체크
void DFS(int depth)
{
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)
{
result[depth] = i;
check[i] = 1; //check[i]를 1로 함으로써 중복이 안되게 설정
DFS(depth + 1);
check[i] = 0;
}
}
}
}
int main(void)
{
scanf("%d %d", &N, &M);
DFS(0);
return 0;
}제출 결과
IT Velog