목차
0x00 백트래킹 알고리즘 설명
0x01 연습문제1 - N과 M
0x02 연습문제2 - N-Queen
0x03 연습문제3 - 부분수열의 합
0x04 STL next_permutation
0x00 백트래킹 알고리즘 설명
현재 상태에서 가능한 모든 선택지를 "따라 들어가며" 탐색하는 알고리즘
탐색하다가 막히면, 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었다고 한다.
상태공간트리(state-space tree)에서 깊이우선탐색(DFS)을 하다가 막히면 자신의 부모노드로 되돌아간다. 참고
오목을 예로 들어 백트래킹의 쓰임새를 알아보자.
나는 파랑돌. 상대는 빨강돌이다. 상대는 직전에 D5를 뒀다. 이번에 나는 어디에 둬야할까?
1 ) B5에 둔다.
그러면 상대는 F5에 둬서 4,3 형태를 갖출 것이다. 상대가 4,3이 되면, 내가 G5 또는 F6에 둬도 진다.
따라서 선택은 틀렸다. 이제 직전상태로 되돌아가서 다른 선택을 해보자.
2) F5에 둔다.
이러면 상대는 B5 or E6 or C4 or G8에 두면서 공격할 것 같다.
지금 이 방식은 일종의 백트래킹이다. 우리는 게임을 할 때 이미 백트래킹 개념을 사용하고 있었다.
참고로 이렇게 생긴 트리를 상태공간트리(state-space tree) 라고 한다.
백트래킹은 상당한 구현력을 필요로하고 실수하기도 쉽다.
재귀의 특성상 틀리더라도 실수한 부분을 찾기 힘들기 때문이다. 연습을 많이 하면 된다.
0x01 연습문제1 - N과 M
문제를 읽으면 '8중 for문으로 구현하면 되겠다' 라는 생각이 날 것이다.
하지만 조금 더 고민해서 백트래킹으로 푸는 방법을 배우자.
아래는 N=4 이고 (1,2,3,4 숫자 사용가능) M=3 (길이가 3인 수열) 인 경우의 백트래킹 과정이다.
1) 처음에는 빈 리스트로 시작한다.
2) 첫 칸에 1을 선택했다. 다음 칸에는 (2,3,4)중에 2를 선택할 수 있다.
이 때 별은 현재 어떤 단계를 탐색하는 중인지 표시한다. 백트래킹은 탐색이 막히면 이전 단계로 되돌아오기 때문에 별 표시가 필요했다.
3) 세 번째 칸에 3을 선택한다.
이제 리스트가 꽉 찼으니 이전 단계로 돌아간다.
4) 세 번째 칸에 4를 선택한다.
이제 리스트가 꽉 찼으니 이전 단계로 돌아간다.
세 번째 칸에 채울 수 있는 숫자 3,4는 둘다 채워봤다. 여기서 할 수 있는걸 다 했으니 또 이전단계로 돌아간다.
5) 두 번째 칸에 새롭게 3을 선택해본다.
이러한 흐름으로 백트래킹을 이해할 수 있을 것이다. 당장 혼자 구현하기는 힘드니 코드를 보며 구현방법을 익히자.
구현 코드
코드를 읽어 보면 재귀적으로 구현됬다. 이 모양은 백트래킹의 전형적인 구조니까 주석을 읽고 잘 익혀두자.
선택한 숫자를 저장하는 int arr 배열
1부터 n까지의 숫자 중에서 '선택 여부'를 저장하는 bool isused 배열
현재 몇 개의 숫자를 선택했는지 인자를 넘기는 재귀 함수 void func(int k )
재귀 함수의 종료 조건(base condition)은 k가 m개를 모두 선택했을 때 이다.
// http://boj.kr/f36567ec0c9f44b4b460b5b29683c27b
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[10];
bool isused[10];
void func(int k){ // 현재 k개까지 수를 택했음.
if(k == m){ // m개를 모두 택했으면
for(int i = 0; i < m; i++)
cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
cout << '\n';
return;
}
for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
if(!isused[i]){ // 아직 i가 사용되지 않았으면
arr[k] = i; // k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k+1); // 다음 수를 정하러 한 단계 더 들어감. 재귀 호출이므로 새로운 스택프레임 생성됨.
isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}func함수의 for문이 핵심이다.
1부터 n까지의 수에 대해 아직 i가 사용되지 않았으면 다음 수를 정하러 한 단계 더 들어간다.
for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
if(!isused[i]){ // 아직 i가 사용되지 않았으면
arr[k] = i; // k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k+1); // 다음 수를 정하러 한 단계 더 들어감
isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
재귀로 다음 수를 정하러 함수를 호출하고 나서 종료되면, 현재 선택했던 수를 사용하지 않았다고 표시한다.
즉, 이전 단계로 돌아오는 것이다.
단 현재 값이 i인 arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없다. 어차피 자연스럽게 다른 값으로 덮힐 예정이기 때문이다.
잘 모르겠다면 함수의 중간 중간 arr, isused, k를 출력한다던가 하는 방식으로 확인하고, (영상으로도 확인)
n과 m시리즈 문제집을 풀어보며 백트래킹 구조에 익숙해지도록 시간을 투자하면 된다.
0x02 연습문제2 - N-Queen
퀸은 상하좌우 그리고 대각선에 위치한 말을 공격할 수 있다.
퀸을 서로 공격할 수 없게 n개 놓을 수 있는 방법 개수를 출력하는 문제다.
즉 퀸이 서로 (1,2) 칸 차이가 있어야 대각선과 열에 걸리지 않는다.
행 마다 퀸이 딱 1개씩 있어야 한다.
4X4 배열에서 상태공간트리를 그려보자
1. A1 칸에 첫 번째 퀸을 하나 놓자.
2. B행에서 가능한 선택지는 2가지다. B3과 B4칸. B3에 두 번째 퀸을 놓자.
C행을 보니 모든 열에서 두 개의 퀸한테 공격당하게 된다.
3. B3은 무르고 A1만 놨던 단계로 되돌리자.
4. B행에서 가능한 B4칸에 두 번째 퀸을 놓자.
5. C행을 보니 가능한 선택지가 C2 뿐이다. C2에 세 번째 퀸을 놓자.
6. D행에서는 네 번째 퀸을 놓을 자리가 없다.
A1에 퀸을 뒀을때의 선택지는 모두 시도한 셈이니 아무것도 안놨을 때로 되돌아가자.
이제 A2에 퀸을 놓아볼 차례다.
이 방식으로 상태공간트리를 채우면 아래의 결과가 나온다.
D행에 퀸을 놓았다면 4번째 퀸인 셈이니까. N=4일 때 답은 2가지라고 할 수 있다.
코드로 구현해보자
cur 번째 행에 퀸을 배치한다는 함수를 구현하자.
int cnt = 0;
//cur 번째 행에 퀸을 배치할 예정이다.
void func(int cur){
if(cur == n){ // 마지막행
cnt++; return;
}
}퀸 2개가 (0,0)과 (1,3)에 있다고 가정하자.
다음 행에는 어느 열에 둬야 하는지 구현하려면 열과 대각선에 대해 생각해야 한다.
1. 먼저 (0,1)과 (2,1)이 같은 열에 있다는걸 어떻게 확인할 수 있을까?
간단히 두 좌표의 y좌표가 일치하는지 확인하면 된다.
2. (3,0)과 (1,2)가 같은 대각선에 있음을 어떻게 확인할까?
왼쪽 하단에서 오른쪽 상단을 잇는 좌표가 대각선을 이루는지 판단한다.
살짝 수학적 관찰이 필요하긴한데, 각 좌표의 x+y가 같으면 대각선에 위치한다.
3. 좌측 상단과 우측 하단을 잇는 대각선에 대해서는 x-y가 같은지 확인하면 된다.
(1,1) 과 (3,3) 은 각각 x-y가 0으로 동일하다.
이렇게 열과 대각선을 일일히 확인하면 O(N)이 추가로 필요하게 된다. 더 나은 방법을 알아보자.
행과 열을 사용됬는지 여부를 저장하는 배열
구현 할 때 어려운 점은 '이 좌표에 퀸을 둘 수 있는지 여부를 판단'하는 부분이다.
이미 놓여진 모든 퀸에 대해 대각선 혹은 열이 겹치는게 있나 확인해야 새 퀸을 놓을 수 있다.
이를 위해 행과 열이 사용됬는지 여부를 저장하는 배열을 두면 편하다.
isused1 : 열에 대응되는 값으로 (x,y)에 퀸이 있으면 isused1[y]값을 true로 만든다.
isused2 : 왼쪽 하단에서 오른쪽 상단을 연결하는 대각선을 검사한다. (x,y)에 퀸이 있으면 isused2[x+y]값을 true로 만든다.
isused3 : 왼쪽 상단에서 오른쪽 하단을 연결하는 대각선을 검사한다. (x,y)에 퀸이 있으면 isused3[x-y+n-1]값을 true로 만든다.
아까 예시로 (1,1) 과 (3,3) 은 각각 x-y가 0으로 동일하다. 고 했는데.
인덱스를 음수로 만들지 않기 위해 n-1이 필요하다.
구현코드
// http://boj.kr/4e7fe4509a3842598592fe4ed79900c0
#include <bits/stdc++.h>
using namespace std;
bool isused1[40]; // column을 차지하고 있는지
bool isused2[40]; // / 방향 대각선을 차지하고 있는지
bool isused3[40]; // \ 방향 대각선을 차지하고 있는지
int cnt = 0;
int n;
void func(int cur) { // cur번째 row에 말을 배치할 예정임
if (cur == n) { // N개를 놓는데 성공했다면
cnt++;
return;
}
for (int i = 0; i < n; i++) { // (cur, i)에 퀸을 놓을 예정
if (isused1[i] || isused2[i+cur] || isused3[cur-i+n-1]) // column이나 대각선 중에 문제가 있다면
continue;
isused1[i] = 1;
isused2[i+cur] = 1;
isused3[cur-i+n-1] = 1;
func(cur+1);
isused1[i] = 0;
isused2[i+cur] = 0;
isused3[cur-i+n-1] = 0;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
func(0);
cout << cnt;
}백트래킹에서 조건에 안맞는 것은 걸러내는 과정을 '가지치기'라고 한다.
가지치기가 여러개면 시간복잡도 계산이 어렵다.
문제를 보고 시간복잡도가 가늠이 안가는데 N이 작아서 백트래킹으로 푸는 문제 같아 보이면,
구현 한 뒤 시간이 가장 오래걸릴 만한 케이스를 돌려봐서 시간 초과가 나는지 확인하자. 이 문제라면 N=14를 넣어보는 것이다.
시간을 로컬에서 측정할 때에는 반드시 Release 모드로 실행을 해야 하고 보통은 서버가 로컬보다 빠르다는 점도 기억하자.
Release 모드 : 프로그램 배포를 위해 디버깅 정보를 실행코드를 넣지 않는다.
속도나 크기 면에서 월등히 유리하다.
디버깅 모드 크기가 릴리즈 모드 크기의 3~4배 정도 파일 크기 차이가 난다.
0x03 연습문제3 - 부분수열의 합
미리 알아둘 점
원소가 n개인 부분 집합의 개수는 2의 n승 개다.
이 원소를 집합에 포함하냐/안하냐 의 선택 횟수를 곱하기 때문이다.
목표
문제의 표현은 부분수열이지만 부분집합을 구하는 것과 동일한 상황이다.
따라서 공집합은 빼고 2의 n승 -1 개의 모든 부분수열의 합이 S와 일치하는지 확인하자.
수열이 [-2, 5, 3] 인 상태공간트리를 그려보자
원 안의 값은 현재 내가 택한 수열의 전체 합이다.
각 상태는 두 갈래로 분기하는데, 왼쪽은 현재 보는 수를 수열에 추가하지 않은 경우이고, 오른쪽은 수열에 추가한 경우다.
1) 먼저 -2를 수열에 추가하지 않았다.
2) 5를 수열에 추가하지 않았다.
3) 3을 수열에 추가하지 않았다. 완성된 수열은 공집합과 같은 [ ] 이고 -2, 5, 3 셋 다 추가하지 않았다.
4) 거슬러 올라가서, 3을 수열에 추가한다. 완성된 수열은 [3] 이고 총합은 3이다.
5) 거슬러 올라가서, 5를 수열에 추가한다.
이 상황에서 먼저 3을 추가하지 않고 완성한 수열 [5]의 합을 확인한다. 총합은 5다.
6) 다음으로 3을 추가해 완성된 수열 [3, 5]의 합을 확인한다. 총합은 8이다.
구현코드
실제 구현을 할 때는 함수의 인자로 현재까지의 합을 넘기도록 했다.
그리고 문제에서 크기가 양수인 부분수열만 센다고 했으니 공집합은 제외해줘야 한다.
따라서 목표합s가 0일때 cnt에서 1을 빼줘야 한다.
// http://boj.kr/792d9af025724ce2912c77e8d56793d1
#include <bits/stdc++.h>
using namespace std;
int n, s;
int arr[30];
int cnt = 0;
void func(int cur, int tot){
if(cur == n){
if(tot == s) cnt++;
return;
}
func(cur+1, tot);
func(cur+1, tot+arr[cur]);
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++)
cin >> arr[i];
func(0, 0);
if(s == 0) cnt--;
cout << cnt;
}
0x04 STL next_permutation
next_permutation 함수로 순열과 조합을 깔끔하게 해결할 수 있다. 레퍼런스
예시를 보면, [ 1, 2, 3] 으로 만들 수 있는 모든 순열을 쉽게 구할 수 있다.
순열
int a[3] = {1, 2, 3};
int main(void) {
do{
for(int i = 0; i < 3; i++){
cout << a[i] << ' ';
}
cout << '\n';
}while(next_permutation(a, a+3));
return 0;
}출력 결과
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
유의점
배열 a가 정렬된 상태로 next_permutation()을 돌려야 모든 경우의 수가 출력된다.
사전 순으로 따졌을 때 제일 마지막일 때 next_permutation()은 false를 반환해서 멈추기 때문이다.
만약 중복된 수가 있따고 해도 사전 순의 결과를 잘 돌려준다.
조합
예를 들어 [1 2 3 4]에서 숫자 2개를 순서 없이 뽑는 모든 경우를 출력하려면 어떻게 짜야할까?
선택 or 선택 안함의 모든 경우의 수를 next_permutation()으로 만들 수 있다.
#include <bits/stdc++.h>
using namespace std;
int ch[4] = {0, 0, 1, 1}; // 4개중에 2개 선택(1)
int main(void) {
do{
for(int i = 0; i < 4; i++){
if(ch[i] == 0){
cout << i+1 << ' ';
}
}
cout << '\n';
}while(next_permutation(ch, ch+4));
return 0;
}출력 결과
1 2
1 3
1 4
2 3
2 4
3 4N과 M시리즈 문제 중에 1,2,5,6 번은 next_permutation() 으로 다시 풀어보자.
N과 M 문제 3, 4, 7, 8은 같은 수를 여러번 써도 되니까 next_permutation()을 쓸 순 없다.
백트래킹 문제집
다음 시간에는 시뮬레이션을 공부한다.
공부 자료 출처 : 바킹독 알고리즘 백트래킹
'알고리즘 > 실전 알고리즘' 카테고리의 다른 글
| 0x0F강 - 정렬2 (0) | 2021.12.18 |
|---|---|
| 0x0E강 - 정렬1 (0) | 2021.12.11 |
| 0x0B강 - 재귀 (0) | 2021.12.08 |
| 0x0A강 - DFS (0) | 2021.12.07 |
| 0x09강 - BFS (0) | 2021.12.07 |