https://www.acmicpc.net/problem/15649
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입출력
- 예제 입력 1
3 1- 예제 출력 1
1
2
3- 예제 입력 2
4 2- 예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3- 예제 입력 3
4 4- 예제 출력 3
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1Solution
#include <iostream>
#define MAX 9
using namespace std;
int N, M;
int MATRIX[MAX];
bool visit[MAX];
void DFS(int count){
if(count == M){
for(int i = 0; i < M; i++){
cout << MATRIX[i] << " ";
}
cout << '\n';
return;
}
for(int i = 1; i <= N; i++){
if(!visit[i]){
visit[i] = true;
MATRIX[count] = i;
DFS(count + 1);
visit[i] = false;
}
}
}
int main(){
cin >> N >> M;
DFS(0);
}최근에 내 약점을 하나 찾았다. 바로 백트래킹.
아예 백트래킹 시리즈를 따로 만들어서 이 백트래킹을 정복 해 볼까 한다. (3분기 때 반드시 해결해야 할 목표로 잡았다.)
간단한 문제다. 순열을 찾는 것.
next_permutation 과 같은 라이브러리 함수를 활용 할 수도 있다. 하지만 드럽게 복잡해진다. 생각보다 라이브러리의 사용이 항상 좋지만은 않다. 어떻게든 조합들을 구 할수는 있겠지만 사전 순의 증가를 기대 할 수는 없다. 즉 또 정렬하고 지지고 볶는 귀찮은 작업이 필요 할 수 있다.
DFS를 활용하면 된다. 어쨌든 입력 자체는 사전 순으로 들어가지 않는가?
int N, M;
int MATRIX[MAX];
bool visit[MAX];
void DFS(int count){
if(count == M){
for(int i = 0; i < M; i++){
cout << MATRIX[i] << " ";
}
cout << '\n';
return;
}
for(int i = 1; i <= N; i++){
if(!visit[i]){
visit[i] = true;
MATRIX[count] = i;
DFS(count + 1);
visit[i] = false;
}
}
}DFS의 전체 코드는 위와 같다. 우선 짧게 설명하면 visit 배열을 통해 방문하지 않았 던 곳에 방문 표시를 해 두고 계속 다음 인덱스들을 방문하는 것이다.
for(int i = 1; i <= N; i++){
if(!visit[i]){
visit[i] = true;
MATRIX[count] = i;
DFS(count + 1);
visit[i] = false;
}
}기존의 DFS 개념을 이해하고 있음에도 어 이게 맞나...싶은 생각이 들 수 있다. 사실 인접행렬을 통한 그래프 탐색과는 조금 다를 수 있다.
만약 N = 10이고 M이 3인 경우를 생각 해 보자.
위의 for문을 통해 처음에는 1번부터 탐색하게 된다. 1번은 처음으로 방문 한 것일 테니 visit 배열에서 false 로 처리 되어 있을 것이다.
그 다음 재귀함수를 통해 count에 1을 더한 채로 DFS가 진행 될 것이다. 똑같은 코드를 만날 것이고 1번은 visit 배열에서 true 처리 되어있으니 i가 2 일때의 for문 부터 똑같은 로직이 반복 될 것이다.
마찬가지로 count가 3이 될 때 까지 재귀가 반복 될 것이고 해당 작업이 끝났을 때 return 처리 되면서 3부터 visit 배열의 false 처리를 할 것이다.
하지만 for문이 끝나지 않았다. 자연스럽게 1번과 2번은 visit 가 true 처리 된 시점에서 다시 4부터 for 문이 돌 것이다. 이런식으로 하나 하나씩 백트래킹 해 가며 값들을 출력 해 나갈 것이다. 1, 2, 3부터 10까지의 값들에 대한 경우들이 모두 출력 된 후 2를 true 처리 한 시점에서 벗어나서 다시 3 부터 처리 하기 시작 할 것이다.
처음에 바로 떠올리기 힘든 개념이지만, 익숙해져야 할 개념이었다. 내가 지금 당장 약하기도 했던...
