백준 16920 - 확장 게임 (C++)

문제

• 문제 링크

  
   BOJ 16920 - 확장 게임 
  

• 문제 요약

$N*M$ 크기의 맵이 주어지고 $P$명의 플레이어 정보가 주어진다.
플레이어 번호 순으로 각 성이 $S_i$만큼 확장할 때, 최종 맵 상태를 구해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ N, M ≤ 1,000$

$1 ≤ P ≤ 9$

$1 ≤ Si ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 너비 우선 탐색(bfs)

풀이

   각 플레이어별로 큐를 관리하고, 다음 이동을 담아줄 별도의 temp 큐 하나를 운용하였다.
맵은 통합으로 관리해 주었고 매 순간마다 각 플레이어 전용 큐 size의 합이 $0$이면 최종 상태가 됨을 판단 하였다.

위 조건이 만족될 때까지 계속해서 시뮬레이션을 돌려주면 된다..이외에 별로 어려운 부분은 없어 보인다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0 }, dx[]{ 0, 0, -1, 1 };
queue <tuple<int, int, int>> Q[10], NQ;
int n, m, p, c[10], d[10];
char M[1001][1001];
 
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> p;
    for (int i(1); i <= p; cin >> d[i++]);
    for (int i(1); i <= n; i++)
        for (int j(1); j <= m; j++)
        {
            cin >> M[i][j];
            if (M[i][j] > 48) Q[M[i][j] - 48].push({ i, j, 0 });
        }
}
void f()
{
    for (int i(1), s{}; i <= p; i++)
        if (s += Q[i].size(); i == p && !s)
        {
            for (int i(1); i <= n; i++)
                for (int j(1); j <= m; j++)
                    if (M[i][j] > 48)
                        c[M[i][j] - 48]++;
            for (int i(1); i <= p; cout << c[i++] << ' ');
            exit(0);
        }
}
void sv()
{
    while (1)
    {
        f();
        for (int i(1); i <= p; i++)
        {
            while (Q[i].size())
            {
                auto [a, b, w](Q[i].front()); Q[i].pop();
                if (w == d[i]) { NQ.push({ a, b, 0 }); continue; };
                for (int j{}; j < 4; j++)
                {
                    int y(a + dy[j]), x(b + dx[j]);
                    if (y && x && y <= n && x <= m && M[y][x] == '.')
                        M[y][x] = i + 48, Q[i].push({ y, x, w + 1 });
                }
            }
            while (NQ.size()) Q[i].push(NQ.front()), NQ.pop();
        }
    }
}
int main()
{
    in();
    sv();
}

comment

끝