백준 15649 N과 M (1) 풀이 (Backtracking)
문제
https://www.acmicpc.net/problem/15649
문제내용
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 2
1
2
3
문제풀이
문제해설
- 순열을 구하는 문제로 재귀함수를 이용하여 백트래킹을 통해서 구하는 문제이다.
- 백트래킹은 보기에는 간단해 보이지만 실행 과정을 직접해보면 이해하기 힘든 경우가 많다.
- 트리 구조로 생각하면서 풀이하는게 이해하기 수월하다.
코드 설명1
#include <iostream>
#include <vector>
using namespace std;
int N; // 주어진 자연수
int M; // 중복없이 뽑는 수
vector<int> result; // 결과 저장
int check[9]; // 방문여부 확인
- 필요한 변수를 선언하고, 헤더를 추가한다.
1.1. result은 정렬된 순열을 담기 위한 변수
1.2. check는 백트래킹을 하면서 이미 방문된 숫자인지 판별하는 변수
코드 설명2
void recur(int num) {
if (num == M) {
print();
return;
}
for (int i = 1; i < N + 1; i++) {
if (check[i] == 0) {
check[i] = 1;
result.push_back(i);
recur(num + 1); // 자식 노드 방문
check[i] = 0;
result.pop_back();
}
}
}
- num을 매개변수로 받아 탐색 깊이를 알 수 있도록 한다.
- 만약 탐색 깊이가 m과 같다면 result에 있는 순열을 출력하고 부모 노드쪽으로 돌아간다.
- 1부터 n까지의 숫자를 탐색하는 for문을 작성한다.
3.1. 만약 i가 방문하지 않았다면 방문 체크한다.
3.2. 방문 체크 후, 현재 깊이에 저장된 result에 i를 추가한다.
3.3. 자식 노드에 방문하기 위해 재귀함수 실행
3.4. 자식 노드에서 돌아오면 방문 체크를 해제한다.
3.4.1. 다른 부모 노드에 방문할 수 있게 하기 위해서 초기화
3.5. 다음 자기 형제 노드의 값이 저장할 수 있게 자신을 제거한다.
그림 예시
다음 예시는 N = 3, M = 2이고, recur(0)이 호출된 내용을 보여준다.
- M=2이고, num이 0이기 때문에 1부터 3까지 숫자를 탐색하는 for문에 들어간다.
- 1번은 방문하지 않았기 때문에 방문을 기록하고 result에 추가한다.
- result = [1]
- 자식 노드에 방문하기 위해 recur(1)를 호출한다.
- M=2이고, num이 1이기 때문에 1부터 3까지 숫자를 탐색하는 for문에 들어간다.
- 1번은 이미 방문했기 때문에 제외된다.
- 2번은 방문하지 않았기 때문에 방문을 기록하고 result에 추가한다.
- result = [1, 2]
- 자식 노드에 방문하기 위해 recur(2)를 호출한다.
- M=2이고, num이 2이기 떄문에 결과를 출력하고 recur(1)로 돌아온다.
- 2번 방문 기록을 취소하고, result에 제거한다.
- result = [1]
- 3번은 방문하지 않았기 때문에 방문을 기록하고 result에 추가한다.
- result = [1, 3]
- 자식 노드에 방문하기 위해 recur(2)를 호출한다.
- M=2이고, num이 2이기 때문에 결과를 출력하고 recur(1)로 돌아온다.
- 3번 방문 기록을 취소하고, result에 제거한다.
- result = [1]
- 더 이상 방문할 곳이 없기 때문에 recur(0)으로 돌아온다.
- 1번 방문 기록을 취소하고, result에 제거한다.
- result = []
- recur(0)의 다음 순서는 2번이고, 2번은 방문하지 않았기 때문에 방문을 기록하고 result에 추가한다.
- result == [2]
- 자식 노드에 방문하기 위해 recur(1)를 호출한다.
코드 설명3
int main() {
// 정보 입력
cin >> N >> M;
// 재귀함수 실행
recur(0);
return 0;;
}
- main에서 num을 0부터 시작하는 재귀함수 호출
전체코드
/*
1. 아이디어
- 재귀함수를 사용해서 문제를 해결
- 벡터를 사용해서 결과를 저장
- 배열로 방문여부 체크
2. 자료구조
- 결과 저장용 벡터
- 방문여부 체크 배열
*/
#include <iostream>
#include <vector>
using namespace std;
int N; // 주어진 자연수
int M; // 중복없이 뽑는 수
vector<int> result; // 결과 저장
int check[9]; // 방문여부 확인
// 결과 출력 함수
void print() {
for (int i = 0; i < result.size(); i++) {
cout << result[i]<<" ";
}
cout << "\n";
}
// 재귀함수
void recur(int num) {
if (num == M) {
print();
return;
}
for (int i = 1; i < N + 1; i++) {
if (check[i] == 0) {
check[i] = 1;
result.push_back(i);
recur(num + 1); // 자식 노드 방문
check[i] = 0;
result.pop_back();
}
}
}
int main() {
// 정보 입력
cin >> N >> M;
// 재귀함수 실행
recur(0);
return 0;;
}