여기를 클릭하면 문제를 볼 수 있습니다.
📕 문제설명
입력 예시를 통해 문제를 이해해보자.
N=4, M=2로 입력이 주어졌다는 것은 1부터 4까지의 자연수 중 중복없이 2개를 골라 길이가 2인 수열을 모두 구하라는 뜻이다.
그러므로 출력으로는 1 2, 1 3, ... , 4 3이 되겠다.
여기서 주의해야할 점은 사전식으로 출력해야한다는 것이다.
📕 문제풀이
조건을 만족하는 수열을 생성하는 방법을 단계적으로 생각해보자.
N=4, M=3이 입력으로 주어졌다고 가정했을 때
생성되는 수열은 1 2 3, 1 2 4, 1 3 2, 1 3 4, 1 4 2, 1 4 3, ... 와 같다.
생각을 좀 더 간단하게 하기 위해 1 2 3, 1 2 4, 1 3 2, 1 3 4만 놓고 생각해보자.
수열을 처음 생성할 때 가장 작은 숫자인 1을 선택하고 중복이 되면 안되므로 그 다음 작은 숫자인 2, 그 다음 작은 숫자인 3이 선택된다. 3이 선택되는 순간 길이가 3이 되므로 M과 동일하므로 출력을 한다. 이렇게 하면 1 2 3을 생성한 것이다.
이 점에서 중복을 피하기 위해 특정한 숫자가 이미 사용되었는지 확인하기 위한 변수가 필요하다는 것을 깨닫게 된다. 또한 수열을 출력하기 위해서 수열을 저장하기 위한 기본적인 배열이 필요하다는 것을 알게 된다. 그러므로 다음과 같은 변수가 필요하다.
bool visited[9] = {0, };: 중복 확인을 위한 배열
int num[9] = {0, };: 수열 출력을 위한 배열
1 2 3을 출력하고 나면 1 2 X꼴의 수열은 1 2 4가 남아 있으므로 3을 버리고 4를 선택하여 1 2 4를 생성하여 출력할 수 있다. 1 2 3과 1 2 4를 출력하고 나면 1 2 X꼴의 수열은 모두 생성한 것이다. 더 이상 생성할 것이 없다. 그러므로 한 칸 더 후퇴하여 1 X X 에서 3을 선택하여 1 3 X꼴의 수열을 생성하면 된다.
이와 같이 길이가 M이 될 때까지 수열을 중복이 없도록 하나씩 생성하여 길이가 M이 되면 출력하고 한칸 물러나고 다른 수를 선택하여 수열을 생성, 출력하고 더 이상 생성할 수 없다면 또 물러나서 생성하고 이런 방식이다.
즉, 이 부분에서 재귀함수를 사용해야 한다는 것을 알 수 있다.
그러므로 다음과 같이 재귀함수를 정의하면 된다.
📕 Code
#include <iostream>
using namespace std;
int num[9] = {0, };
bool visited[9] = {0, };
int n, m;
void backtracking(int cnt)
{
if(cnt == m) // 길이가 m이라면 출력
{
for(int i=0; i<m; i++)
printf("%d ", num[i]);
printf("\n");
return;
}
for(int i=1; i<=n; i++)
{
if(!visited[i]) // 중복이 되지 않는다면
{
visited[i] = 1; // 그 수를 사용하고
num[cnt] = i;
backtracking(cnt+1); // 수열의 그 다음 칸을 채우러간다.
visited[i] = 0;
}
}
}
int main(void)
{
scanf("%d %d", &n, &m);
backtracking(0);
return 0;
}📕 후기
정말 설명을 개똥같이 한다. 이 설명을 읽고 이해를 하는 사람이 있다면 그는 정말로 머리가 좋으며 사람 말을 잘 이해하는 사람일 것이다.
backtracking과 같이 재귀 함수를 사용하는 경우는 말로 표현하기가 정말 어렵다. (backtracking문제는 설명할 게 안된다...ㅠㅠ)
그러므로 이 문제는 본인의 설명을 읽는 것보다 N과 M을 예시로 든 다음 손으로 직접 그 함수의 흐름을 적어보는 것이 더 빨리 이해될 것이다.
왜냐하면 본인도 누군가의 설명을 읽어서 이해하기 보다는 직접 적으면서 이해를 했기 때문이다.
다음 사진은 본인이 처음 이해하고자 했을 때 손으로 직접 적어가며 흐름을 파악한 사진이다. (정말로 설명을 읽는 것보다 이게 더 도움이 된다.)
📕 관련문제
해당 문제를 온전히 이해하고 풀 수 있다면 다음 문제들은 자매품이다. 보너스로 맞추고 가시길...
