확장게임
구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.
게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.
각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.
자신의 영토를 라운드당 늘릴 수 있을만큼 늘릴 때 더이상 늘릴 수 없을 때 까지 진행한 뒤, 각 땅을 얼마나 먹었나를 계산하는 문제이다.
꽤나 애먹은 문제이다. 환장게임 역시나 풀이를 보면 비교적 쉽게 접근 할 수 있었으나, 나의 경우 상당히 고전했다. 거두절미하고 풀이로 들어가보자.
문제 풀이
문제풀이에는 BFS를 이용했다. 필자의 경우 DFS로 풀어보겠다고 고생했으나 해결하지 못했다. 또한 문제의 특성이 BFS를 사용하는 것이 좀 더 자연스럽다고 다가와진다.
핵심적인 내용은 다음과 같다.
다음과 같은 영토가 존재한다고 생각해보자. 이 때 숫자는 플레이어의 영토를 의미하며 각 플레이어는 라운드당 1칸씩 늘어날 수 있다고 가정하자 그렇다면, 한 라운드 이후의 모습은 어떤식으로 바뀔까?
당연히도 위와 같이 바뀔 것이다. 그럼 만일 플레이어 1의 이동제한이 2였다면 어땠을까?
위와 같았을 것이다. 여기서 나는 DFS를 이용하여 다음과 같은 의문이 있었다.
위의 표시된 1의 경우에는 확장될 가능성이 3개가 있다. 내가 고민했던 것은 "과연 어느부분으로 부터 확장을 받아야 최대한 확장할 수 있는가?" 에 대한 의문이었다. 이 부분을 해결하고자 상당히 많은 고민을 했었는데 놀랍게도 BFS에서는 위의 의문이 보장된다.
어찌 생각해보면 당연하다.
위와 같은 상황을 가정하자. 과연 파란 점에는 누가 먼저 도착할까? BFS에 대해 이해하고 있다면 여러 상황에 따라 결과가 다를 것이라는 걸 알수 있을 것이다.
우선 큐에 1을 PUSH하고 탐색을 돌린다면 1이 먼저 도착할 것이다. 가로막는 것이 없기 때문이다.
반대로 큐에 2를 PUSH하고 탐색을 돌린다면 2가 먼저 도착할 것이다. 똑같은 이유에서이다.
그렇다면 만일 큐에 1과 2를 같이 넣고 BFS를 돌리면 어떻게 될까? 자 생각해보자.
다음과 같이 탐색을 시작할 것이다. 이해를 돕기 위해 다음 상황도 표현해보자.
위와 같은 상황이 될 것이다. 그렇다 BFS에서는 FIFO의 특성에 의해 더 가까이 위치한 탐색지점에서 출발한 탐색이 먼저 도착하는 것을 보장한다.
이 특징을 잘 이용하면 라운드당 이동제한만큼만 BFS를 계속해서 진행시켜주면 된다.
이럴 경우 가장 최 외각의 노드들은 큐에 잔류하여 다음 라운드를 기다릴 것이다.
위의 상황에서 7, 8, 9, 10은 큐에 계속 남아있음을 기억하자.
그러나 플레이어 마다 라운드 횟수가 다르기 때문에 각 플레이어 마다의 큐를 따로 생성하여 관리해야할 것이다.
코드
// BOJ 16920 확장 게임
#include <iostream>
#include <queue>
#include <vector>
#define Y first
#define X second
#define MAX 1'000
using namespace std;
typedef pair<int, int> pii;
int N, M, P;
int S[10];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char map[MAX][MAX];
void printMap(){
cout << "printMAP :: \n";
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cout << map[i][j] << " ";
}
cout << "\n";
}
}
void init(){
cin >> N >> M >> P;
for(int i=1; i<=P; i++){
cin >> S[i];
}
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> map[i][j];
}
}
}
void BFS(){
init();
queue<pii> Q[10];
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(map[i][j] == '.' || map[i][j] == '#') continue;
Q[map[i][j] - '0'].push({i,j});
}
}
while (1){
bool flag = false;
for(int p=1; p<=P; p++){
int movement = S[p];
while (!Q[p].empty() && movement){
movement--;
int size = Q[p].size();
for(int j=0; j<size; j++){
int cur_y = Q[p].front().Y;
int cur_x = Q[p].front().X;
Q[p].pop();
for(int i=0; i<4; i++){
int nex_y = cur_y + dy[i];
int nex_x = cur_x + dx[i];
if(nex_x < 0 || nex_y < 0 || nex_y >= N || nex_x >=M) continue;
if(map[nex_y][nex_x] != '.') continue;
flag = true;
Q[p].push({nex_y, nex_x});
map[nex_y][nex_x] = map[cur_y][cur_x];
}
}
/*for Print*/
// printMap();
// int x;
// cin >> x;
}
}
if(!flag) break;
}
int res[10] = {0};
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(map[i][j] == '.' || map[i][j] == '#') continue;
res[map[i][j] - '0']++;
}
}
for(int i=1; i<=P; i++){
cout << res[i] << " ";
}
cout << "\n";
}
int main(){
BFS();
return 0;
}초기에 맵에 있는 모든 플레이어의 땅을 각 플레이어의 큐에 넣어두고 이동제한을 둔 뒤 BFSF를 돌릴 수 있을 때 까지 돌리면 된다.
빈 땅으로만 이동할 수 있도록 제한을 두면 별도의 VIS 배열도 필요가 없어지게 된다.
SUMMARY
- BFS / DFS 의 특징을 잘 이해하기.
