백준 알고리즘 15649번: N과 M(1) [C++]

문제 출처: www.acmicpc.net/problem/15649

15649번: N과 M (1)

1. 코드

#include <iostream>
#include <string>

using namespace std;

string arr;
bool input[9];
int n, m;

void solution(int position)
{
	if (position == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (!input[i])
		{
			input[i] = true;
			arr.push_back(i + '0');

			solution(position + 1);

			input[i] = false;
			arr.pop_back();
		}
	}
}

int main(void)
{
	cin >> n >> m;
	solution(0);
	return 0;
}

(실행)

2. 풀이

위 실행 과정의 그림은 n = 4, m = 3인 상태에서 첫 번째 요소가 1일 경우이다. 1부터 시작하여 두 번째, 세 번째, 네 번째 요소에 접근을 시도하며 모든 경우의 수를 탐색을 한다. 그리고 비교하는 경우의 수가 많아질수록 반복문으로 표현하는 것은 점점 더 복잡해지기 때문에 재귀 함수로 구현하였다. 위 실행 과정을 참고하며 아래의 코드에 대한 설명을 읽어보면 조금 더 이해하기 쉬울 것이다.

string arr;
bool input[9];
int n, m;

필요한 변수는 위와 같은데 n과 m은 사용자에게 입력받을 변수이고 arr은 입력을 받은 값에 대한 출력을 담당하고 배열 input은 어떠한 수가 사용되었는지 확인하는 용도의 배열이다. 그리고 input의 크기는 문제에서 n과 m에 입력될 수는 1 이상 8 이하이기에 9로 정했다.

cin >> n >> m;
solution(0);

그리고 n과 m을 입력받고 solurion를 호출하는데

void solution(int position)
{
	if (position == m)
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << " ";
		cout << '\n';
		return;
	}

함수 인자로 0을 받았기에 현재 position의 값은 0이다. 그리고 만약 position의 값과 m이 같다면 배열 arr을 출력 후 함수를 종료한다. 즉, 저 if문에 대한 조건을 충족하면 함수 종료를 한다.

for (int i = 1; i <= n; i++)
{
	if (!input[i])
	{
		input[i] = true;
		arr.push_back(i + '0');

		solution(position + 1);

		input[i] = false;
		arr.pop_back();
	}
}

그리고 1부터 n까지 반복을 하는데 배열 input은 어떠한 수가 사용되었는지 확인하는 용도이기에 사용하지 않은 input값이 있다면 현재 input [ i ]에 대한 값을 true로 하여 사용했다는 표시를 해주고 문자열 arr에 i에 '0'을 더해서 문자로 변환시킨 뒤 그 문자를 문자열 요소의 맨 뒤에 추가해준다. 그리고 이것을 종료문이 나올 때까지 position의 값을 1 증가시킨 값을 인자로 가진 자기 자신의 함수를 호출(재귀)한다. 재귀 함수가 종료가 되면 input [ i ] 값을 false로 바꾸어 사용하고 있지 않다고 표시를 해준다. 그리고 문자열 arr의 요소 중 맨 뒤에 있는 요소를 제외시킨다.

문자열 arr의 실행 과정

만약 코드 설명을 보고 잘 이해가 되지않으면 위 gif를 참고하길 바란다.

3. 느낀 점

아직 재귀 함수를 잘 다루지 못해서 코드를 완성하는데 많은 시간이 소모되었다. 조금씩이라도 재귀 함수에 대해 능숙해지는 연습을 해야겠다.