[APS][C++] BOJ G2 16920번 확장 게임 (feat. 우선순위 큐)

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

---

문제

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

 

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

 

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

 

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

입력

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

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

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

출력

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

제한

• $ 1 ≤ N, M ≤ 1,000 $
• $ 1 ≤ P ≤ 9 $
• $ 1 ≤ S_i ≤ 10^9 $

---

풀이

• 너비우선탐색(BFS)을 이용한 영역 확장 문제 (Flood Fill 문제)
• 단, round, turn, player 등에 의해 플레이 순서가 정해져 있으므로 일반 큐가 아닌 우선순위큐 사용
• 확장이 모두 끝나면, 즉 맵이 모두 채워지면 플레이 종료
• 플레이가 종료되면, 각 플레이어마다 차지한 땅의 크기를 카운팅 후 출력

---

코드

#include <climits>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

struct Play {
  long long player;
  long long turn;
  long long check;
  long long y;
  long long x;
  long long id;

  bool operator<(const Play& right) const {
    if (turn != right.turn) return turn > right.turn;
    if (player != right.player) return player > right.player;

    return id > right.id;
  }
};

int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};

long long map[1001][1001];

int main() {
  int count[10] = {0};
  long long current_id = 0;

  int n, m, p;
  cin >> n >> m >> p;

  int S[10] = {0};
  for (int i = 1; i <= p; i++) {
    cin >> S[i];
  }

  priority_queue<Play> pque;

  for (int i = 0; i < n; i++) {
    string temp;
    cin >> temp;

    for (int j = 0; j < m; j++) {
      if (temp[j] == '.') {
        map[i][j] = -1;
      } else if (temp[j] == '#') {
        map[i][j] = 0;
      } else {
        int temp_ply = int(temp[j]) - 48;
        map[i][j] = temp_ply;
        pque.push({temp_ply, 1, 1, i, j, current_id++});
      }
    }
  }

  while (!pque.empty()) {
    Play now = pque.top();
    pque.pop();

    for (int i = 0; i < 4; i++) {
      long long ny = now.y + dy[i];
      long long nx = now.x + dx[i];

      if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
      if (map[ny][nx] != -1) continue;

      if (now.check == S[now.player] * now.turn) {
        map[ny][nx] = now.player;
        pque.push(
            {now.player, now.turn + 1, now.check + 1, ny, nx, current_id++});
      } else {
        map[ny][nx] = now.player;
        pque.push({now.player, now.turn, now.check + 1, ny, nx, current_id++});
      }
    }
  }

  for (int i = 1; i <= p; i++) {
    for (int row = 0; row < n; row++) {
      for (int col = 0; col < m; col++) {
        if (map[row][col] == i) {
          count[i]++;
        }
      }
    }
  }

  for (int i = 1; i <= p; i++) {
    cout << count[i] << " ";
  }

  return 0;
}

---

결과

---

오답 원인

• 우선순위큐는 들어온 순서를 보장하지 않는다. ➡️ 즉, 우선순위큐는 오퍼레이터에 따라 출력 순서가 정해지지만, 오퍼레이터에서 명시되지 않은 우선순위(ex. 입력 순서 등)에 대해서는 순서를 보장할 수 없다.
• 내가 틀린 이유 역시 들어온 순서를 보장할 수 없기에 문제가 발생하였다. ➡️ 들어온 순서에 대한 우선순위를 보장하기 위해 구조체 내에 id라는 변수를 추가하여 들어온 순서를 지정했으며, 오퍼레이터에서도 id가 작을수록 우선순위가 높을 수 있도록 배치하여 해결하였다.
• 테스트케이스가 통과되더라도 우선순위큐에서 들어온 순서는 보장되지 않는다는 점을 명심하자!!

---