[C++] BOJ 16920 / BFS (확장게임, BFS 이동 제한)

문제 분석

 

https://www.acmicpc.net/problem/16920

플레이어 수는 최대 9명이며, 플레이어 끼리 성을 하나 씩 가진 채로, 성을 상하좌우로 확장시키는 게임이다.

중요한 조건은 이동할 수 있는 칸수를 정해준다는 것이다. 기본적인 BFS는 1칸으로 제한되어 있다고 생각하면 이해하기 쉽다.

2칸 이상 씩 이동할 수 있게 조건이 주어진 경우를 구현하는데에 시간을 많이 썼다. 해결하고 생각해보면 간단한 것이었는데 난이도를 보고 어려울 것이라 지레짐작 했던 것이 악영향을 끼쳤다. 기본적인 것을 응용하는 것 또한 중요하다는 점을 깨달았다.

 

해결 방법

성이 이동할 수 있는 칸이 제한되어 있기 때문에, 이 조건을 맞추기 위해서는 BFS 이동 횟수를 제한해야 한다.

종료 조건이 모든 플레이어의 성이 이동할 수 없을 때 인데, 이 조건 때문에 배열 전체를 탐색하면서 0이 있는지 확인하면 무한루프에 빠지게 된다. 벽에 둘러 쌓인 영토는 항상 0이기 때문이다.

그래서 본인은 배열 값을 bfs 돌리기 전 후로 전부 더한 sum 값을 비교하여 값이 바뀌지 않으면 break 해주었다.

코드에 for 문이 반복되어 있어서 가독성이 떨어지지만, bfs()함수와 sum 값을 비교하여 값을 도출해내는 부분만 중점적으로 보면 이해하기 쉬울것이다.

 

코드

#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int board[1001][1001];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
long long s[10];	// s의 최대값이 10^9 이므로 long long으로 선언
int ans[10];
queue<tuple<int,int,int>> q[10];	// <x좌표,y좌표,이동칸수>
int n,m;

void bfs(int player) {
    queue<tuple<int,int,int>> tmpQ;
    while(!q[player].empty()) {
        tuple<int,int,int> cur = q[player].front();
        q[player].pop();
        if(get<2>(cur) >= s[player]) {
            tmpQ.push({get<0>(cur), get<1>(cur), 0});
            continue;
        }
        for(int dir=0;dir<4;dir++){
            int nx = get<0>(cur) + dx[dir];
            int ny = get<1>(cur) + dy[dir];
            int lim = get<2>(cur);
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(board[nx][ny] != 0) continue;
            board[nx][ny] = player;
            q[player].push({nx,ny,lim+1});
        }
    }
    q[player] = tmpQ;	// 다음 bfs에 사용해야하므로, 저장해둔 테두리 블록들 push
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int p;
    char c;

    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 >> c;
            if(c == '.') {
                board[i][j] = 0;
            }else if(c == '#') {
                board[i][j] = -1;
            }else {
                board[i][j] = c - '0';
                q[c-'0'].push({i,j,0});
            }
        }
    }
 
    while(1) {
        int sum1=0, sum2=0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                sum1 += board[i][j];
            }
        }
        for(int i=1;i<=p;i++) {
            bfs(i);
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                sum2 += board[i][j];
            }
        }
        if(sum1 == sum2) break;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(board[i][j] == -1 || board[i][j] == 0) continue;
            ans[board[i][j]]++;
        }
    }
    for(int i=1;i<=p;i++) {
        cout << ans[i] << " ";
    }
}