문제 출처

1. 문제설명

  • 게임은 N*M 크기의 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다.
  • 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다.
  • 게임은 라운드가 이루어져 있고, 각 라인드마다 플레이어는 성을 확장한다.
    • 제일 먼저 플레이어 1이 확장하고, 2가 확장을 하는 식으로 진행된다.
  • 플레이어는 자신의 성이 있는 곳에서 상,하,좌,우 인접한 칸으로 이동할 수 있다.
    • 벽이나 다른 플레이어의 성이 있는 곳으로는 이동할 수 없다.
    • 성을 다 건설한 이후엔 다음 플레이어가 턴을 갖는다.
  • 모든 플레이어가 더 이상 확장을 할 수 없을 때 게임이 끝난다.



2. 알고리즘 설계

  • BFS문제이다.
  • 사전에 플레이어의 번호만큼 큐를 생성해, 좌표를 저장한다.
  • 플레이어의 수만큼 큐를 탐색하면서,
  • 확장할 수 있는 칸을 플레이어의 번호로 채워준다.
  • 만약 어떤 플레이어의 큐가 비어있지 않으면, 확장하지 못한 것이다.
    • 종료 조건!



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

typedef struct info
{
    int y, x;
};

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int row, col, p;
int area[10];
int len[10];
char arr[1000][1000];
queue<info> q[10];

void bfs()
{
    while (1)
    {
        for (int t = 1; t <= p; t++)
        {
            int dist = len[t];
            while (!q[t].empty() && dist--)
            {
                int qs = q[t].size();
                for (int i = 0; i < qs; i++)
                {
                    int cx = q[t].front().x;
                    int cy = q[t].front().y;
                    q[t].pop();
                    for (int k = 0; k < 4; k++)
                    {
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx] == '.')
                        {
                            arr[ny][nx] = t + '0';
                            q[t].push({ny, nx});
                            area[t]++;
                        }
                    }
                }
            }
        }
        bool finish = true;
        for (int i = 1; i <= p; i++)
        {
            if (!q[i].empty())
            {
                finish = false;
                break;
            }
        }
        if (finish)
            break;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> row >> col >> p;
    for (int i = 1; i <= p; i++)
        cin >> len[i];

    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
        {
            cin >> arr[i][j];
            if ('1' <= arr[i][j] && arr[i][j] <= '9')
            {
                q[arr[i][j] - '0'].push({i, j});
                area[arr[i][j] - '0']++;
            }
        }
    bfs();
    for (int i = 1; i <= p; i++)
        cout << area[i] << " ";
    return 0;
}