[백준 - 16920] 확장 게임 - C++

분류: BFS, BFS 순차 실행, 시작점이 여러개인 BFS, 시작점이 여러 종류인 BFS /

 

문제

문제 링크

문제 설명

구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다.

게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다.

각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸으로 확장한다. 플레이어 i는 자신의 성이 있는 곳에서 S_i칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 위, 왼쪽, 오른쪽, 아래로 인접한 칸으로만 이동할 수 있으며, 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다. 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.

모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다. 게임판의 초기 상태가 주어졌을 때, 최종 상태를 구해보자.

입력

첫째 줄에 격자판의 크기 N, M과 플레이어의 수 P가 주어진다. 둘째 줄에는 S₁, S₂, ...S_P가 주어진다.

다음 N개의 줄에는 게임판의 상태가 주어진다. '.'는 빈 칸, '#'는 벽, '1', '2', ..., '9'는 각 플레이어의 성이다.

모든 플레이어는 적어도 하나의 성을 가지고 있으며, 게임에 참가하지 않는 플레이어의 성이 있는 경우는 없다.

출력

플레이어 1이 가진 성의 수, 2가 가진 성의 수, ..., P가 가진 성의 수를 공백으로 구분해 출력한다.

 

풀이

#include <iostream>
#include <queue>
using namespace std;

struct xy {int x, y;};
int dx[] = {1, 0 ,-1, 0};
int dy[] = {0, 1, 0 ,-1};
int N, M, P;
int S[10];
char board[1000][1001];
queue<xy> Qs[10];
int area[10];

bool allEmpty() {
    for(auto Q:Qs)
        if(!Q.empty())
            return false;
    return true;
}

void bfs(int p) {
    queue<xy> &Q = Qs[p];
    int s = S[p];
    while(!Q.empty() && s--) {
        int size = Q.size();
        while(size--) {
            xy cur = Q.front(); Q.pop();
            for(int i=4; i--;) {
                int nx = cur.x + dx[i], ny = cur.y + dy[i];
                if(nx<0 or nx>=N or ny<0 or ny>=M) continue;
                if(board[nx][ny] != '.') continue;
                area[p]++;
                board[nx][ny] = '#';
                Q.push({nx, ny});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> P;
    for(int i=1; i<=P; i++) cin >> S[i];
    for(int i=0; i<N; i++) {
        cin >> board[i];
        for(int j=0; j<M; j++) {
            if(isdigit(board[i][j])) {
                int p = board[i][j] - '0';
                Qs[p].push({i, j});
                area[p]++;
            }
        }
    }

    while(not allEmpty())
        for(int i=1; i<=P; i++)
            bfs(i);
    
    for(int i=1; i<=P; i++) 
        cout << area[i] << ' ';
}

각각 플레이어에 대해 순차 BFS를 수행한다.

나름 새로웠던 점은 순차 BFS를 각 플레이어마다 `S`번 실행한다는 점이었다.

• 모든 플레이어가 더이상 움직일 수 없을 때(`allEmpty()`) 까지 플레이어 순서대로 턴을 돌며 영역 확장(main의 while문)
  • 플레이어는 플레이어 턴마다 다음을 수행(`bfs`)
    • 더 이상 못움직이거나(`Q.empty()`) `Si` 번 순차 실행을 했으면 종료
    • 4 방향으로 퍼지고 빈 공간이라면 가고 벽이거나 숫자가 있으면 pass
    • 벽으로 마킹, 영역 넓이 증가(`area[p]++`)

죄다 섞어놨지만 쉬웠다.

벽으로 마킹하지 않고 각자 숫자로 마킹해서 주변에 2개 이상이면 잡아 먹는다던지 했으면 더 재밌는 문제였을것 같다.

 

# cin.ignore()

처음에 `string board[1000]`로 선언해서 `getline(cin, board[i])`으로 받으려 했다.

`cin`은 버퍼에 개행문자를 남겨놔 마지막 `cin`인 `cin >> S[P]`후에 버퍼에 개행문자가 남아있다.

이걸 `board[0]`이 받아 `board[0] = '\n'`으로 길이가 0인 스트링이 되어버린다.

이럴때 버퍼를 비워줘야하는데 `cin`이 끝나고 `getline`이 시작하기 전에 `cin.ignore()`을 해주면된다.

cin >> S[P]; // 버퍼에 개행문자 남아있음
cin.ignore(); // 버퍼 비움
getline(cin, board[0]); // 다음 문자열 받음