[백준 16920번] 확장 게임

문제 링크: https://www.acmicpc.net/problem/16920

16920번: 확장 게임

<문제 풀이> BFS 알고리즘

라운드마다 각 플레이어 별로 BFS를 돌리면 되는데, i번 플레이어의 최대 이동 횟수를 큐가 비었는지를 검사하는 while문에 같이 넣고 1씩 감소시켜주면 됩니다.

+ 최대 이동 횟수를 while문에 같이 넣어주면 플레이어의 모든 성을 최대 이동 횟수까지 움직여볼 수 있음

+ while문을 한번 돌 때 큐 안에는 플레이어의 각 성에서 움직인 거리가 같은 정점들로 구성되어 있습니다.

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
#define X first 
#define Y second 
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0 , -1, 0};
vector<pair<int, int> > player[10]; 
int res[10];
int s[10]; 
char board[1000][1000];
int n, m, p;
 
void bfs() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] != '.' && board[i][j] != '#') {
                player[board[i][j] - '0'].push_back({ i, j });
            }
        }
    }
    queue< pair<int, int > > Q[10];
    for (int i = 1; i <= p; i++) {
        for (auto castle : player[i]) {
            Q[i].push({ castle.X, castle.Y });
            res[i]++;
        }
    }
 
    while (true) { //라운드 시작
        bool success = false;
        for (int i = 1; i <= p; i++) { //1번 플레이부터 시작
            int s_len = s[i]; //i번 플레이어의 최대 이동 횟수
            while (!Q[i].empty() && s_len--) { // i번 플레이어 BFS 
                int Q_size = Q[i].size();
                for(int j=0; j<Q_size; j++){
                    auto cur = Q[i].front(); Q[i].pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
                        if (board[nx][ny] == '.') { // 성을 건설할 수 있으면
                            Q[i].push({ nx, ny });
                            board[nx][ny] = board[cur.X][cur.Y];
                            res[i]++;
                            success = true;
                        }
                    }
                }
            }
 
        }
        if (!success) break;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    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 >> board[i][j];
        }
    }
    bfs();
   
    for (int i = 1; i <= p; i++) {
        cout << res[i] << ' ';
    }
  
    return 0;
}