백준 16920번 [확장 게임](C++) -yes6686- 티스토리

백준 문제 풀이: 16920 (확장 게임)

---

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

문제 설명:

여러 명의 플레이어가 각각 주어진 이동 속도만큼 자신의 영역을 확장하는 턴 기반 보드 게임입니다. 맵에는 벽(#)이 있을 수 있고, 이미 다른 플레이어가 점령한 칸은 차지할 수 없습니다. 모든 플레이어가 더 이상 영역을 확장할 수 없을 때 게임이 종료되며, 종료 시점에 각 플레이어가 점령한 칸 수를 출력해야 합니다.

이 문제는 BFS와 다중 큐를 통해 각 플레이어의 독립적인 확장을 시뮬레이션하는 방식으로 해결할 수 있으며, 플레이어별 속도 제어가 핵심입니다.

---

문제 해결 코드

// 확장 게임 (BFS 방식 다중 큐 시뮬레이션)
#include <iostream>
#include <queue>
using namespace std;

int parr[10];                   // 플레이어의 최대 이동 거리
int arr[1001][1001];            // 게임 보드 상태 (0: 미점령, -1: 벽, 1~9: 플레이어 번호)
int ans[10];                    // 각 플레이어의 점령 칸 수
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m, p;
queue<pair<int, int>> q[10];     // 플레이어별 BFS 큐

void go() {
    // 초기 각 플레이어의 위치를 큐에 삽입
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] > 0) {
                q[arr[i][j]].push({ i, j });
            }
        }
    }

    while (true) {
        bool moved = false;

        for (int player = 1; player <= p; player++) {
            if (q[player].empty()) continue;
            queue<pair<int, int>> next_q;

            for (int step = 0; step < parr[player]; step++) {
                int sz = q[player].size();
                if (sz == 0) break;

                for (int i = 0; i < sz; i++) {
                    int x = q[player].front().first;
                    int y = q[player].front().second;
                    q[player].pop();

                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];

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

                        arr[nx][ny] = player;
                        next_q.push({ nx, ny });
                        moved = true;
                    }
                }

                // 다음 레벨로 진행
                swap(q[player], next_q);
            }
        }

        if (!moved) break;  // 모든 플레이어가 확장을 못 했으면 종료
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> p;

    for (int i = 1; i <= p; i++) {
        cin >> parr[i];  // 각 플레이어의 확장 속도
    }

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] >= '1' && s[j] <= '9') {
                arr[i][j] = s[j] - '0';
            } else if (s[j] == '#') {
                arr[i][j] = -1;
            } else {
                arr[i][j] = 0;
            }
        }
    }

    go();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] > 0) {
                ans[arr[i][j]]++;
            }
        }
    }

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

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘: 각 플레이어에 대해 독립적인 BFS를 수행하며, 턴 단위로 최대 이동 거리만큼 보드를 확장합니다. 이는 멀티큐 BFS 방식으로, 각 플레이어가 동시에 움직이되 우선순위는 플레이어 순서대로 유지합니다.
• 구현 세부사항: `parr[i]`는 각 플레이어의 최대 확장 거리이며, `arr[x][y]`는 보드 상태를 저장합니다. 각 플레이어의 BFS 진행 상태를 큐 `q[i]`에 저장하며, 한 턴에 최대 `S`번까지 확장하도록 `for (int step = 0; step < parr[player]; step++)`를 사용합니다.
• 시간 복잡도 분석: O(n ⋅ m ⋅ p), 각 칸마다 최대 한 번만 점령되며, 최대 플레이어 수(9명)만큼의 큐 순회가 반복되므로 효율적으로 작동합니다.

---

결과

입력에 따라 각 플레이어가 점령한 칸 수를 공백으로 구분하여 출력합니다.

예시 입력:

5 5 2
1 1
1.#..
..#2.
##..#
..#.#
.....

예시 출력:

4 14

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!