BOJ 15649 : N과 M (1) - 순열 permutation

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15649

 

순열을 구하는 문제이다.

서로 다른 N개중에 M을 선택하는 경우의 수를 의미하고 순서가 상관이 있다.

그리고 중복이 없어야 한다.

 

N = M이면 팩토리얼이 된다.

(서로 다른 N개를 모두 나열하는 경우의 수)

 

예제 입력 2를 예로 4개 중 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

순서에 의미가 있으므로 1 2 와 2 1이 다르다.

 

경우의 수 문제는 대부분 재귀 호출로 해결한다.

 

먼저 첫번째를 선택하면 다음 재귀에서는 선택하지 못하도록 해야한다.

따라서 숫자들이 현재 선택된 상태인지 확인하는 배열 visit이 필요하다.

 

그리고 최종적으로 M개를 선택하였을 때, 선택한 숫자들을 출력해야하므로,

선택한 숫자를 저장할 배열 list가 필요하다.

 

아래의 코드를 보고, DFS의 Level 0인 경우를 생각해보자.

for (int i = 1; i <= N;i++) 
{
	if (visit[i] == 1) continue;
		
	list[L] = i;

	visit[i] = 1;
	DFS(L + 1);
	visit[i] = 0;
}

Level 0에서 i = 1 부터 N까지 훑어볼텐데, visit[1] = 0 (아직 아무 숫자도 선택하지 않았으므로)이 된다.

따라서 list[Level = 0] = 1이 저장되고, 다음 dfs에서 1을 선택하지 못하도록 visit[1] = 1로 체크한다.

 

Level 1 DFS에서도 i = 1부터 N까지 모두 훑어본다.

i = 1 에서 visit[1] = 1 에 의해 list[Level = 1]에는 1을 선택할 수 없다.

continue에 의해 i = 2가 되고, List[2] = 2로 저장된다.

 

List[0] = 1, List[1] = 2가 되고,

다음 Level = 2 = M이므로, List를 출력해주면 N = 4, M = 2의 첫 번째 출력인 1, 2가 출력된다.

 

이제 Level 2 dfs는 종료되었다. Level 1에서 i = 2가 종료되었고, visit[2] = 0이 된다.

그리고 i = 3으로 넘어가서 1, 3을 출력하게 된다.

 

i = 4까지 모두 출력하면, dfs Level 1의 for문 i = 1 ~ N을 모두 종료하게 된다.

 

이제 dfs Level 0의 i = 1이 끝났으므로, visit[1] = 0이 되고, i = 2의 차례가 된다.

즉, 2 1 / 2 3 / 2 4 가 출력되게 된다.

 

visit[1] = 0이 됨에 따라 Level 1에서 1을 List에 저장할 수 있다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

int N, M;

int list[10];
int visit[10];

void outputList()
{
	for (int i = 0; i < M;i++) printf("%d ", list[i]);
	putchar('\n');
}

void DFS(int L)
{
	if (L == M)
	{
		outputList();
		return;
	}

	for (int i = 1; i <= N;i++) 
	{
		if (visit[i] == 1) continue;
		
		list[L] = i;

		visit[i] = 1;
		DFS(L + 1);
		visit[i] = 0;
	}
}

int main(void)
{
	scanf("%d %d", &N, &M);

	DFS(0);

	return 0;
}