mo1lusca의 블로그
[백준] N과 M (시리즈) - C++ 본문
DFS를 열심히 연습했으니 이번엔 DFS를 활용한
백트래킹 알고리즘을 배우자!
백트래킹은 모든 경우의 수를 탐색하는 알고리즘인데,
여기서 중요한 포인트는 DFS나 BFS같이 모든 노드를 방문해 탐색하는 것이 아니라
가망이 없는 경로는 버려서 효율적으로 해를 찾는다는 것이다!
백트래킹 연습을 위해 N과 M 시리즈 문제(12문제)를 풀어보자.
대체로 비슷한 문제들이어서 몇 문제만 풀어놓아도 금방 풀린다.
글이 상당히 기니 주의하기 바란다.
1번 문제
https://www.acmicpc.net/problem/15649
N개의 수 중 M개를 선택해 만들 수 있는 수열들을 구한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
bool used[9];
void backtrack(int depth) {
if (depth == m) { // <1>
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
if (!used[i]) { // <2-0>
used[i] = true; // <2-1>
arr[depth] = i; // <2-2>
backtrack(depth + 1); // <2-3>
used[i] = false; // <2-4>
}
}
}
int main() {
cin >> n >> m;
backtrack(0);
return 0;
}arr 배열은 수열을 저장하는 배열이다.
used 배열은 현재 수열을 만드는 과정 중 해당 숫자를 사용한 적이 있는지 저장한다.
<1> : depth는 수열 내의 몇 번째 수를 고르고 있는지를 나타낸다. 만약 m개의 수를 골랐다면 다 고른 것이므로 for문을 통해 수열을 출력 후 return 한다.
<2-0> : 앞서 사용되지 않은 수에 대해 이하의 코드를 실행한다.
<2-1> : 해당 수를 사용했다고 표시한다. 밑에서 호출할 재귀함수에서 이 수를 다시 사용하지 않게 하기 위함이다.
<2-2> : 수열을 만들어 저장하는 배열 arr의 depth번째 값으로 i를 넣는다.
<2-3> : backtrack 함수를 재귀호출한다. 매개변수로 depth + 1을 넘겨주어 수열의 수를 하나씩 쌓는 느낌으로 실행한다.
이 호출은 for문 안에 있기에 i값에 따라 분기를 나누어 함수를 호출하게 된다.
<2-4> : backtrack 함수의 재귀호출이 끝난 뒤, 다음 분기에서 사용할 수 있도록 used배열을 false로 원상복구 해준다.
2번 문제
https://www.acmicpc.net/problem/15650
2번 문제는 순열인 nPm을 구하는 1번 문제와 달리, 조합인 nCm을 구하는 문제이다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = start; i <= n; i++) { // <1>
arr[depth] = i;
backtrack(depth + 1, i + 1);
}
}
int main() {
cin >> n >> m;
backtrack(0, 1);
return 0;
}1번 문제에서는 중복 방지를 위해 used 배열을 사용했지만, 2번 문제에서는 순서 상관없이 이미 선택한 수보다 큰 수를 선택 (오름차순) 하기 때문에, 매개변수 start로 중복을 방지한다.
<1> : 매개변수로 받은 start부터 for문을 돌린다. 이를 통해 depth번째 값보다 큰 값만 다음에 올 수의 후보로서 분기를 가진다.
3번 문제
https://www.acmicpc.net/problem/15651
위 문제들과 비슷하지만, 중복을 허용한다는 조건이 있다!
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
void backtrack(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
arr[depth] = i;
backtrack(depth + 1);
}
}
int main() {
cin >> n >> m;
backtrack(0);
return 0;
}
1, 2번 문제에서 각각 중복 방지 역할을 하던 used, start를 모두 없앤다.
리미트 언록!!
4번 문제
https://www.acmicpc.net/problem/15652
3번 문제와 비슷하지만, 수열이 내림차순이 아니어야 한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = start; i <= n; i++) {
arr[depth] = i;
backtrack(depth + 1, i);
}
}
int main() {
cin >> n >> m;
backtrack(0, 1);
return 0;
}코드 자체는 2번 문제와 매우 흡사하다.
단지 backtrack 함수를 재귀호출할 때, 두 번째 인자로 i + 1이 아닌 i를 넘겨준다. 이를 통해 start값에 현재 인덱스값을 넘겨줄 수도 있게 되었으며, 중복을 허용하여 비내림차순을 구현할 수 있다.
5번 문제
https://www.acmicpc.net/problem/15654
5번 문제부터 본격적으로 입력값을 통해 수열의 수를 정하게 한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
bool used[9];
int input[9];
void backtrack(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
used[i] = true;
arr[depth] = input[i];
backtrack(depth + 1);
used[i] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> input[i];
}
sort(input + 1, input + n + 1);
backtrack(0);
return 0;
}로직은 1번 문제와 같으므로, 입력만 잘 받고 잘 처리만 하면 된다..
input 배열에 입력을 받는데, 오름차순으로 준다는 보장이 없으므로 sort를 해주어야 한다.
backtrack 함수 내에서도 arr[depth] 값으로 i가 아닌 input[i]를 저장한다는 것 외에는 특별한 점이 없다.
6번 문제
https://www.acmicpc.net/problem/15655
이제 슬슬 규칙성이 보이기 시작하는데...
역시나 6번 문제는 2번 문제와 같은 로직을 사용한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = start; i <= n; i++) {
arr[depth] = input[i];
backtrack(depth + 1, i + 1);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> input[i];
}
sort(input + 1, input + n + 1);
backtrack(0, 1);
return 0;
}2번 문제 복붙 수준이긴 하지만, 우리는 복붙 단축키를 연습하는 게 아니라 백트래킹을 연습하는 것이기에....
웬만하면 생각을 하며 짜도록 하자.. 참고로 필자는 다 지우고 처음부터 짰다..
7번 문제
https://www.acmicpc.net/problem/15656
3번 문제와 같은 로직을 사용한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
void backtrack(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
arr[depth] = input[i];
backtrack(depth + 1);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> input[i];
}
sort(input + 1, input + n + 1);
backtrack(0);
return 0;
}솔직히 이제 쓸 말도 없다..
solved.ac 레이팅 올리기에 참 편한 시리즈구나 생각했다.
사실 죄다 실버라 그렇게 많이 올라가진 않는다.
8번 문제
https://www.acmicpc.net/problem/15657
4번 문제와 같은 로직을 사용한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = start; i <= n; i++) {
arr[depth] = input[i];
backtrack(depth + 1, i);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> input[i];
}
sort(input + 1, input + n + 1);
backtrack(0, 1);
return 0;
}4의 배수번째 문제니 다음 문제는 유형이 바뀌어서 나올 것이라고 짐작할 수 있다.
9번 문제
https://www.acmicpc.net/problem/15663
5번 문제와 비슷한 로직을 사용한다.
더 생각해봐야 할 것은, 이제는 입력이 중복으로 주어지는 경우도 있다는 것이다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
bool used[9];
int input[9];
void backtrack(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
if (!used[i]) {
if (i > 1 && input[i] == input[i - 1] && !used[i - 1]) { // <1>
continue;
}
used[i] = true;
arr[depth] = input[i];
backtrack(depth + 1);
used[i] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> input[i];
}
sort(input + 1, input + n + 1);
backtrack(0);
return 0;
}backtrack 함수 내에서 중복 검사를 수행해주어야 한다.
<1> : 일단 i가 1보다 큰지 검사한다. 그래야 i - 1번째 인덱스에 무사히 접근할 수 있기 때문이다.
그리고 i번째 input과 i - 1번째 input이 같은지 검사한다. (input은 정렬된 상태이다.)
그리고 i - 1번째 input이 사용되지 않았는지도 검사해야 한다.
아무튼 이 모든 조건을 통과했다면, 이 수는 중복이기 때문에 건너뛰어야 한다!!
10번 문제
https://www.acmicpc.net/problem/15664
마찬가지로 6번 문제와 같은 로직에, 중복검사를 추가한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
bool used[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
int prev = -1;
for (int i = start; i < n; i++) {
if (used[i]) {
continue;
}
if (input[i] == prev) {
continue;
}
prev = input[i];
used[i] = true;
arr[depth] = input[i];
backtrack(depth + 1, i + 1);
used[i] = false;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> input[i];
}
sort(input, input + n);
backtrack(0, 0);
return 0;
}여기서는 중복검사를 위해 prev이라는 변수를 만들었다. 이 변수는 현재 depth에서 방금 뽑은 값을 저장한다.
사실 이렇게 prev을 사용하는 방법이 9번 문제에서 사용했던 if문 떡칠 코드보다 삼백배는 깔끔하다.
prev 변수가 하는 역할은 전체적으로 비슷하다. 임의의 값 x가 뽑히고 나면, 그다음 인덱스가 같은 x더라도,
input[i] == prev에서 걸러져서 같은 수열이 두 개 생기는 걸 방지한다.
참고로 prev의 초기값이 -1인 이유는, 단지 맨 처음 검사되는 input값과 겹치지 않기 위함이다.. 안 겹칠 자신만 있다면 어떤 값을 넣어도 된다.
11번 문제
https://www.acmicpc.net/problem/15665
7번 문제와 같은 로직에, 중복검사를 추가한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
void backtrack(int depth) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
int prev = -1;
for (int i = 0; i < n; i++) {
if (input[i] == prev) {
continue;
}
prev = input[i];
arr[depth] = input[i];
backtrack(depth + 1);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> input[i];
}
sort(input, input + n);
backtrack(0);
return 0;
}같은 수로 수열을 만들어도 되기 때문에 used를 사용하지 않았지만, 중복검사는 그대로 해주어야 한다!
12번 문제
https://www.acmicpc.net/problem/15666
대망의 마지막 문제이다. 8번 문제와 같은 로직에, 중복 검사를 추가한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[9];
int input[9];
void backtrack(int depth, int start) {
if (depth == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
int prev = -1;
for (int i = start; i < n; i++) {
if (input[i] == prev) {
continue;
}
prev = input[i];
arr[depth] = input[i];
backtrack(depth + 1, i);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> input[i];
}
sort(input, input + n);
backtrack(0, 0);
return 0;
}이 정도는 껌이다.
처음의 4문제만 풀면 나머지 8문제는 쉽게 슥슥 풀리는 것 같다.
다른 문제로도 백트래킹 연습을 해보아야겠다.
'PS' 카테고리의 다른 글
| [백준] 1931 회의실 배정 - C++ (0) | 2025.06.18 |
|---|---|
| [백준] 1541 잃어버린 괄호 - C++ (0) | 2025.06.18 |
| [백준] 7576 토마토 - C++ (0) | 2025.06.05 |
| [백준] 2606 바이러스 - C++ (1) | 2025.06.03 |
| [백준] 1260 DFS와 BFS - C++ (0) | 2025.06.03 |