백야극광: 한붓그리기 알고리즘① - dfs
</br>
오빠가 서울에 학교를 다녀 자취를 하고 있다~~ 이번에 집에 잠시 내려 와서 오랜만에 같이 지냈다. 게임에 관심이 많아 휴학 중에 게임 회사를 다니기도 했는데, 그래서 그런지 게임을 여러가지 해보더라.
이번에도 휴대폰 게임을 몇 개 하고 있길래 한 번 봤는데, 그 중 하나가 전투 시스템이 특이해서 관심이 갔다.
최근 모바일 게임은 유저들의 돈을 빠르게 모을 수 있는ㅋㅋ 수집형 게임이 대세다.
안 그래도 요즘 모바일 게임은 비슷한 게 많아서… 전투 시스템에서 특별한 재미나 차별성이 없다면 유사 게임, 망겜이라 불린다.
https://www.alchemystars.kr/about.html
이번에 볼 게임은 “백야극광”이라고 퍼즐 RPG 모바일 게임이다.
한붓그리기 퍼즐
한붓그리기 퍼즐이라고 불리더라. 별로인 턴제 게임들은 대충 캐릭터 스킬 눌러 주고 넘기는데, 백야극광은 퍼즐 부분이 꽤 특색 있다.
빨강, 노랑, 초록, 파랑 타일들이 맵에 뿌려져 있고 그 중 한 색을 선택해 연결해서 콤보를 쌓는다. 당연히 콤보가 클 수록 좋다.
맵을 한 번 클리어한 경우 자동 전투 기능도 있다. 아무래도 컴공이다 보니 이런 거 보면 어떤 식으로 돌아가는 건가 생각하게 되는데, 자동 전투는 어떻게 프로그래밍되어 있을까, 간단하게 생각해 보기로 했다.
- 가장 큰 콤보 찾기
- 도착 지점은 스킬을 사용했을 때 적 위치에 맞을 수 있게
캐릭터 마다 스킬 범위 등이 다양할 것이므로 2번 조건은 나중에 보도록 하고, 일단 1번은 알고리즘 공부할 때 많이 보던 거랑 비슷한 게 할 수 있을 같다.
</br>
문제 만들기
우선 간단히, 입력으로 맵이 주어졌을 때 최대 콤보를 찾는 프로그램을 만들어 보자. 맵은 정사각형이며, 최대 크기는 10이다.
테스트 케이스다. 일단 RGB의 3가지 색상이 있다고 치고, 유저 캐릭터가 있는 곳은 색이 없는 타일이다.
5
GGGRB
RGGBR
BORGR
BBGGB
RRBGR
입력은 위와 같이 정사각형 맵의 가로 크기와, 문자(R, G, B)로 색을 구분하고 ‘O’는 유저의 위치라고 하자.
1 2 3
8 O 4
7 6 5
따라서 유저는 자신을 둘러싼 타일 8개 중 하나를 선택해서 콤보를 시작할 수 있다. 탐색 순서는 위와 같이 시계 방향으로 하자.
여기서 최고 콤보는 초록색이다. 방식은 다양하지만 9개 모두 연결될 수 있으므로 콤보 수는 9다.
파란색의 경우 최대 콤보가 4다. 6, 7, 8 에서 시작 가능하지만 7, 8에서 시작할 때 최대 콤보를 쌓을 수 있다.
빨간색은 더 연결될 것들이 없으므로 1, 4에서 모두 콤보가 1이다.
</br>
풀이
탐색 문제다. dfs를 활용하면 쉽게 풀릴 것 같다.
#include <bits/stdc++.h>
using namespace std;
int N;
char mmap[12][12];
int check[12][12];
int maxCombo; char maxColor;
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
*/
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");
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];
if( s[j] == 'O' ){
startI = i+1;
startJ = j+1;
}
}
}
inp.close();
/* Print Map
for(int i = 0; i < N+2; i++){
for(int j = 0; j < N+2; j++){
cout << mmap[i][j]<<' ' ;
}
cout<<endl;
}
*/
for(int i = 0; i < 8; i++){
// cout << "----------------------START" << endl;
for(int i = 0; i < N+2; i++)
for(int j = 0; j < N+2; j++)
check[i][j] = 0;
int x = startI + moveI[i];
int y = startJ + moveJ[i];
check[x][y] = 1;
func(x, y, mmap[x][y], 1);
}
out << maxColor << ' ' << maxCombo << endl;
out.close();
}
전체 코드다.
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
*/
다음을 방문할 때의 움직임을 정의한 배열이다.
// in main()
for(int i = 0; i < 8; i++){
// cout << "----------------------START" << endl;
for(int i = 0; i < N+2; i++)
for(int j = 0; j < N+2; j++)
check[i][j] = 0;
int x = startI + moveI[i];
int y = startJ + moveJ[i];
check[x][y] = 1;
func(x, y, mmap[x][y], 1);
}
입출력 부분은 빼고, dfs 부분을 보자. 방문했는 지 확인하는 check[][]를 초기화 하고, 유저 위치에서 1 ~ 8 타일을 순서대로 func()을 실행하는 for문이다.
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;
}
}
}
dfs를 수행하는 함수다. 만약 현재 콤보가 저장된 최대 콤보보다 크다면 값을 업데이트한다. 마찬가지로 1 ~ 8 타일을 순서대로, 만약 아직 방문하지 않은 노드이고 색이 현재 찾고 있는 색과 같다면 방문한다.
확인해 보기 위한 출력 결과다.
방문 순서는 위 그림처럼 끝을 방문 했다가 되돌아가며 잘 돌아간다.
</br>
간단한 조건으로 일단 만들어 보았다! 다음에는 최적화가 가능하다면 더 하고, 조건도 추가해서 만들어 보자.
</br>
댓글남기기