[C/C++] 백준 10974번 모든 순열

문제 풀이

이 문제는 '순열'을 이용한 것임. 수를 나열하는 데, 중복해서 사용할 수는 없고 순서가 다르면 다르게 보는 것임.

예를 들어 {1,2}라는 숫자 집합이 있다고 할 때, 2개씩 나열하는 순열은 1,2 / 2,1와 같이 같은 숫자를 사용할 수 있는 것임.

 

코드로 설명하면 아래와 같음.

void D(int cnt)
{
	if (cnt==N+1) // N+1: 4
	{
		for (int i=1; i<=N; i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	else
	{
		for (int i=1; i<=N; i++)
		{
			if (visited[i]==false)
			{
				a[cnt]=i;
				visited[i]=true;
				D(cnt+1);
				visited[i]=false;
			}
		}
	}
}

위에 보면 if문에는 종료 조건이 있고, 종료 조건 때는 그동안 모아 온 재료를 '출력' 또는 '동작'

else 조건은 재료를 넣어주는 것이라고 지난 중복 순열 때 얘기드렸음.

 

그럼, 이번에는 중복 순열하고 다름. 중복 순열은 else에다가 for문으로 모든 재료를 하나씩 넣어주면 되었는 데, 지금은 한번 사용한 재료는 사용할 수 없는 것임. 그럼 어떻게 else에 재료가 들어가게 구성해야 할까?

1) 사용했으면 재사용되지 않도록 체크한다.

2) 그리고 재귀 함수를 지나면 풀어준다.

 

2번이 무슨 말인지 이해가 안 될 것임.

예를 들어 10 20 30을 나열하는 순열이 있다고 하자.

카운터 1일 때 10이 나열되었고, 2일 때 20, 3일 때 30이 나열되었다.

 

10 20 30 [카운터 1 때 10 사용 및 체크, 카운터 2 때 20  사용 및 체크, 카운터 3 때 30 사용 및 체크]

10 30 20 [카운터 3때 30 체크 해제, 카운터 2 때 20 체크 해제, 카운터 2때 30 사용 및 사용 체크, 카운터 3 때 20 사용 및 체크]

이런 식으로 구조가 진행됨. 따라서 사용 체크 해제는 반드시 필요한 부분임. 체크 해제해주고 풀어주고 하면서 순서가 바뀌는 것임. 

 

아래와 같이 visited[i]에 체크해 주고 재귀 함수 지나면 다시 풀어주고 있음. 이 구조 잘 기억해 둬야 함. 순열에는 visited[i]체크가 위아래로 감싸고 있고, 조건에 visited[i]==false라는 조건이 있음.

 

처음에는 잘 이해 안 돼도 잘 따지다 보면 이해됨. 그런데 나도 오랜만에 푸는 거라 못 풀면 어떡하지 하면서 풀었던 문제인 듯. 기본 중에 기본이니까 잊지 말도록 하자.

	else
	{
		for (int i=1; i<=N; i++)
		{
			if (visited[i]==false)
			{
				a[cnt]=i;
				visited[i]=true;
				D(cnt+1);
				visited[i]=false;
			}
		}
	}

소스코드

#include <iostream>
#include <vector>
#define MAX 8
using namespace std;

int N;
int M;
int a[MAX];

void D(int cnt)
{
	if (cnt==M+1)
	{
		for (int i=1; i<=M; i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	else
	{
		for (int i=1; i<=N; i++)
		{
			a[cnt]=i;
			D(cnt+1);
		}
	}
}
		
int main() {
	cin>>N>>M;
	D(1);
    return 0;
}