📃 문제: 백준 15649_N과 M(1)
백준 15649는 Backtracking의 개념을 이용해 풀 수 있는 문제이다.
Backtracking은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.
Backtracking의 핵심 개념은 가능성이 없으면 되돌아가는(Pruning) 과정이 포함된다.
입력) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
https://www.acmicpc.net/problem/15649
출력)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
📖 풀이 사고 과정
조건을 만족하는 가능한 모든 수열을 탐색하여 출력하면 되므로, 직관적으로 생각해봤을 때 아래처럼 순차적으로 탐색해가면 된다. DFS의 느낌도 있다. 맨 처음에 1로 시작하는 배열 -> 순서대로 2, 3, 4를 넣는다.
1로 시작하는 배열의 모든 경우의 수를 조합했으므로 이번에는 2로 시작하는 배열도 같은 방식으로 가능한 배열 조합을 생성한다.
이걸 코드로 구현한다면, 이미 사용한 원소는 '사용 처리'를 해줘서 중복된 배열을 탐색하지 않도록 하고, 배열 생성이 완료되었으면 다음 루틴에서 해당 원소를 다시 사용할 수 있게 해당 원소를 '미사용 처리' 해주는 방식으로 순차적으로 탐색해주면 된다.
👩💻 구현 코드(c++ 사용)
위 풀이 사고 과정대로 소스코드로 아래처럼 구현할 수 있다.
이때, func(k) 호출 시 k == M 을 만족해서 func(k)이 return된 경우는 길이가 M개인 배열이 하나 완성된 상태이다.
이때, 다음 배열 조합에서 사용 처리(isused[i] = true)했던 원소를 다음 배열 조합에서 이용할 수 있도록 다시 미사용 처리 해주는 과정을 잊으면 안된다!
진행 과정을 시각적으로 관찰하려고 단계마다 로그를 찍어보았다.
#include <iostream>
using namespace std;
/*1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열*/
int N, M;
int arr[10];
bool isused[10];
void func(int k) {
if (k == M) {
cout << "finish." << endl;
for (int i = 0; i < M; i++) {
cout << arr[i] << " ";
}
cout << '\n';
return;
}
for (int i = 1; i <= N; i++) {
if (!isused[i]) {
arr[k] = i;
cout << "arr[" << k << "]=" << arr[k] << ' ';
// 사용 처리
isused[i] = 1;
cout << "isused[" << i << "]=" << isused[i] << ' ';
func(k + 1);
// 길이가 M인 배열 생성 끝나면, 다시 미사용 상태로 초기화
isused[i] = 0;
cout << "isused[" << i << "]=" << isused[i] << ' ';
}
}
cout << '\n';
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
func(0);
return 0;
}
코드 실행 로그는 아래와 같은데,
첫번째 for문
arr = [1] -> 1 사용처리 -> arr = [1,2] -> 2 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 2 미사용 처리
arr = [1] -> 1 사용처리 -> arr = [1,3] -> 3 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 3 미사용 처리
arr = [1] -> 1 사용처리 -> arr = [1,4] -> 4 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 4 미사용 처리
arr[1] 미사용 처리
딱 위까지의 과정이 아래 도식의 노란색 부분만큼의 작업을 수행한 것이다.
for문에서 i=1부터 시작하여, 1로 시작하는 배열을 생성한다. 그 후 사용했던 2, 3, 4를 차례로 미사용처리 한 다음에, 2로 시작하는 배열 조합을 생성하기 위해 1을 미사용 처리(반납)하는 과정을 한번 실행하는 동작이다.
두번째 for문
arr = [2] -> 2 사용처리 -> arr = [2, 1] -> 1 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 1 미사용 처리
arr = [2] -> 2 사용처리 -> arr = [2,3] -> 3 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 1 미사용 처리
arr = [2] -> 2 사용처리 -> arr = [2,4] -> 4 사용처리 -> func(2)에 도달하여 길이가 M(=2)인 배열 완성 -> 1 미사용 처리
arr[2] 미사용 처리
. . .
해당 작업을 수행하면서 변화하는 값을 로깅해보면 아래와 같다.
arr[0]=1 isused[1]=1 arr[1]=2 isused[2]=1 finish.
1 2
isused[2]=0 arr[1]=3 isused[3]=1 finish.
1 3
isused[3]=0 arr[1]=4 isused[4]=1 finish.
1 4
isused[4]=0
isused[1]=0 arr[0]=2 isused[2]=1 arr[1]=1 isused[1]=1 finish.
2 1
isused[1]=0 arr[1]=3 isused[3]=1 finish.
2 3
isused[3]=0 arr[1]=4 isused[4]=1 finish.
2 4
isused[4]=0
isused[2]=0 arr[0]=3 isused[3]=1 arr[1]=1 isused[1]=1 finish.
3 1
isused[1]=0 arr[1]=2 isused[2]=1 finish.
3 2
isused[2]=0 arr[1]=4 isused[4]=1 finish.
3 4
isused[4]=0
isused[3]=0 arr[0]=4 isused[4]=1 arr[1]=1 isused[1]=1 finish.
4 1
isused[1]=0 arr[1]=2 isused[2]=1 finish.
4 2
isused[2]=0 arr[1]=3 isused[3]=1 finish.
4 3
isused[3]=0
isused[4]=0
[Execution complete with exit code 0]