BOJ 15654 : N과 M (5) - 순열 permutation

 

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/15654

 

 

 

N과 M (1)은 1~N으로 순열을 출력했다면, 이번엔 특정 input에 대해서 순열을 출력하면 된다.

 

사전 순으로 증가하는 순서로 출력해야 하므로, input을 입력받고 정렬하자.

N이 작기 때문에 단순한 O(N²) 정렬로 해도 큰 무리가 없다.

#include <stdio.h>

int N, M;

int list[10];
int visit[10];
int input[10]; /* input 저장 */

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] = input[i]; /* i 대신 input[i] */

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

int main(void)
{
	scanf("%d %d", &N, &M);
	
	for (int i = 1; i <= N; i++) scanf("%d", &input[i]);

	/* 정렬 */
	for (int i = 1; i <= N - 1; i++)
	{
		for (int k = i + 1; k <= N; k++)
		{
			if (input[i] > input[k])
			{
				int tmp = input[i];
				input[i] = input[k];
				input[k] = tmp;
			}
		}
	}

	DFS(0);

	return 0;
}