백야극광: 한붓그리기 알고리즘② - Branch and Bound
</br>
1편에 이어서~~
전 포스트에서 백야극광 전투 시스템 퍼즐의 알고리즘을 간단히 알아 봤다. 가로, 세로, 대각 방향으로 이동 가능하며, 가장 높은 콤보를 찾는다.
1 2 3
8 O 4
7 6 5
dfs를 통한 완전탐색(brute force)으로 모든 경우를 다 알아 보았고, 탐색 순서는 위와 같았다.
Branch and Bound(분기 한정법)
Lower Bound <= 값 <= Upper Bound
완전탐색이 나무의 모든 가지를 뿌리부터 천천히 다 본다면, 브랜치 앤 바운드는 적당히 가지치기를 해주는 알고리즘이다.
좀 더 똑똑한 완전탐색이라고 볼 수 있다. 만약 이 길이 가능성이 없는 게 눈에 뻔히 보인다면, 굳이 그 길을 탐색할 필요는 없다. 또, 좀 더 좋아 보이는 길을 먼저 간다면 이후 가지치기에 수고를 또 덜 수 있을 것이다. 정렬이 필요하므로 보통 우선순위 큐를 사용하게 된다.
수행 시간은 줄지만, 보조 자료가 필요하게 되기 때문에 공간 복잡도는 늘게 된다.
</br>
Bound 추가
그럼 이전의 완전탐색 알고리즘에서 어떤 바운드를 추가할 수 있는가~~
위에서 말 했듯이
- 가장 유망한 길 먼저
- 가능성이 없는 길은 잘라내기
가 포인트이므로,
</br>
가장 유망한 길 먼저
만약 입력으로 이런 맵이 들어 왔다고 보자!
초록색이 딱 봐도 너무 많아서 당연히 초록색이 답일 것 같으므로 초록색을 먼저 탐색하면 좋을 것이다.
</br>
가능성이 없는 길은 잘라내기
위에서 유망한 길을 먼저 찾았으므로, 이는 현재의 Upper Bound가 된다.
그런데 만약 현재의 Upper Bound 콤보가 초록색으로 10인데, 맵에서의 빨간색 타일의 총 개수가 9개라면 빨간색 길은 탐색할 가치가 없다. 아무리 많이 해도 10까지는 쌓을 수 없기 때문이다.
</br>
코드
따라서 입력을 받을 때 각 색 마다 타일 개수를 저장을 한다.
이후, 맵에서 제일 많은 자리를 차지하는 타일을 먼저 탐색한다. 그로 통해 얻은 Upper Bound로 가능성 없는 가지들을 잘라가며 나머지를 탐색한다.
#include <bits/stdc++.h>
using namespace std;
int N;
char mmap[12][12];
int check[12][12];
int maxCombo; char maxColor;
map<char, int> colors;
int moveI[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int moveJ[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
/*
1 2 3
8 O 4
7 6 5
*/
struct P{
int x;
int y;
int c;
P(int x, int y, int c): x(x), y(y), c(c) {}
};
struct cmp{
bool operator()(P p1, P p2){
return p1.c < p2.c;
}
};
void func(int x, int y, char c, int d){
if( d > maxCombo ){
maxCombo = d;
maxColor = c;
}
// cout << x << ' ' << y << ' ' << c << ' ' << d << endl;
for(int i = 0; i < 8; i++){
int nextX = x + moveI[i];
int nextY = y + moveJ[i];
if( check[nextX][nextY] == 0 && mmap[nextX][nextY] == c ){
check[nextX][nextY] = 1;
func(nextX, nextY, c, d+1);
check[nextX][nextY] = 0;
}
}
}
int main(){
ifstream inp;
inp.open("1.inp");
ofstream out;
out.open("1.out");
colors.insert(pair<char, int>('R', 0));
colors.insert(pair<char, int>('G', 0));
colors.insert(pair<char, int>('B', 0));
colors.insert(pair<char, int>('Y', 0));
colors.insert(pair<char, int>('O', 0));
inp >> N;
for(int i = 0; i < N+2; i++)
mmap[i][0] = '\u0000';
for(int i = 0; i < N+2; i++)
mmap[0][i] = '\u0000';
int startI, startJ;
for(int i = 0; i < N; i++){
string s;
inp >> s;
for(int j = 0; j < N; j++){
mmap[i+1][j+1] = s[j];
colors[s[j]]++;
if( s[j] == 'O' ){
startI = i+1;
startJ = j+1;
}
}
}
inp.close();
priority_queue< P, vector<P>, cmp > pq;
for(int i = 0; i < 8; i++){
int x = startI + moveI[i];
int y = startJ + moveJ[i];
int c = colors[mmap[x][y]];
P p = P(x, y, c);
pq.push(p);
}
while( pq.size() ){
// cout << "----------------------START" << endl;
P p = pq.top();
if( p.c >= maxCombo ){
for(int i = 0; i < N+2; i++)
for(int j = 0; j < N+2; j++)
check[i][j] = 0;
check[p.x][p.y] = 1;
func(p.x, p.y, mmap[p.x][p.y], 1);
}
pq.pop();
}
out << maxColor << ' ' << maxCombo << endl;
out.close();
}
전체 코드다.
</br>
// map으로 타일의 색과 타일 수를 저장한다.
map<char, int> colors;
colors.insert(pair<char, int>('R', 0));
colors.insert(pair<char, int>('G', 0));
colors.insert(pair<char, int>('B', 0));
colors.insert(pair<char, int>('Y', 0));
colors.insert(pair<char, int>('O', 0));
// in input for(), 입력 받을 때마다 더해 줌
colors[s[j]]++;
// 탐색을 시작할 후보 타일들을 저장할 구조체 P
struct P{
int x;
int y;
int c;
P(int x, int y, int c): x(x), y(y), c(c) {}
};
// priority queue에 타일 수가 많은 순으로 저장한다.
struct cmp{
bool operator()(P p1, P p2){
return p1.c < p2.c;
}
};
priority_queue< P, vector<P>, cmp > pq;
추가된 부분이다. 브랜치 앤 바운드를 위해 추가적으로 필요한 자료로 맵을 사용했고, 가능성 있는 순으로 탐색하기 위해 우선순위 큐를 사용한다.
while( pq.size() ){
// cout << "----------------------START" << endl;
P p = pq.top();
if( p.c >= maxCombo ){
for(int i = 0; i < N+2; i++)
for(int j = 0; j < N+2; j++)
check[i][j] = 0;
check[p.x][p.y] = 1;
func(p.x, p.y, mmap[p.x][p.y], 1);
}
pq.pop();
}
유저 위치의 8개의 타일을 탐색할 때, 우선순위 큐에서 먼저 나오는 순으로 탐색한다.
현재의 Upper Bound인 maxCombo보다 탐색하려는 타일 수가 더 많다면 가능성이 있으므로 탐색을 수행한다.
이전과 같은 테스트 케이스로 비교해 보자.
확인해 보기 위한 출력 결과다.
2, 3, 5번 타일인 초록색이 맵에서 가장 많으므로 먼저 탐색했다. 여기서 Upper Bound가 9로 업데이트 되었고, 빨간 타일과 파란 타일은 맵에서 9개보다 적었으므로 탐색되지 않았다.
</br>
간단하게 바운드를 추가해 보았다. 다음에는 적의 위치나 스킬 등도 고려해 보자.
</br>
댓글남기기