[16920] 확장 게임

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

16920번: 확장 게임

<문제>

naive하게 구현하면 시간초과가 가능할지에 대한 판단을 분명하게 내리지 않고, 더 나은 방법으로 접근했다.

naive한 접근이라면, 맵을 매번 순회하며 queue에 target을 push하여 bfs의 초기화를 수행하는 방법이다.

가령 3번을 탐색한다면, 모든 3번 성의 좌표를 queue에 push하기 위해 O(N^2)의 복잡도를 소모하는 셈인데

N=1000이므로 turn이 몇백개만 넘어가면 2초를 넘기기 쉽다.

다만, 2초라는 시간제한이 꽤 애매해서, naive한 방법이 통과되지 않을것이라는 확신을 갖지는 못했다.

turn의 최대값이 몇천, 몇만까지 나오지 않기 때문이었고 시간복잡도가 O(N^2 + K)의 형태라면

N^2을 기준으로의 최악의 경우에는 K가 줄어들것 같았다.(정확히는, N^2의 최악과 K의 최악은 독립적일것 같았다)

 

그래서 더 나은 방법이 있는지를 고민하기 시작했고, 얼마 지나지 않아 더 나은방법의 단서를 찾았다.

사실 "더 나은 방법", 즉 naive하지 않은 효율적인 방법의 아이디어는 꽤 간단한데...

 

[3]턴에 어떤 정점 (y, x)가 [2]번 플레이어 영역으로 포함되었다고 가정하자.

3턴이 종료된 이후, 즉 4턴부터 게임이 끝날때까지 (y, x)는 2번 플레이어 영역에 아무런 영향을 미치지 못한다.

 

이를 최적화에 적용할 수 있는만큼 일반화하면, 아래와 같다.

[i]턴의 탐색에 필요한 정점은 [i-1]턴째에 추가된 정점이다

 

그외의 사항은 기존의 문제와 동일하다.

turn이 입력에서의 값으로 제한되었을때의 2차원 4방향 bfs를 진행하면 된다.

위 최적화가 적용된 부분은, 아래 코드의 vector<pair<int, int>>를 보면 된다.

가령, v[3] = {4, 7}이 있다면, 이는 아래의 의미를 갖는다.

"직전의 3번 플레이어의 탐색에서 (4, 7)이 추가되었고, 동시에 이번 탐색의 시작점이다."

 

정확히는 0부터 시작하지만, 어쨋든 vector에는 저러한 의미를 갖도록 구성해주었으며, 이를 위해

bfs의 탐색중 추가된걸 현재 queue에도 넣고, vector에도 넣었다.

당연한 말이지만, queue는 pop()하지만 vector는 탐색중 erase하지 않으므로

P번의 탐색이 진행된 후에도 남아있게 된다. 구현할때 clear()의 위치에는 유의할 필요가 있겠다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, p, s[10], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[1001][1001];
bool visited[1001][1001];
typedef struct {
    int y, x, turn;
} state;
vector<pair<int, int>> v[10];
int main(void) {
    int i, j;
    cin >> n >> m >> p;
    for (i = 0; i < p; i++) cin >> s[i];
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if ('1' <= a[i][j] && a[i][j] <= '9') {
                v[a[i][j] - '1'].push_back({i, j});
            }
        }
    }
    while (1) {
        bool flag = true;
        for (i = 0; i < p; i++) {
            if (v[i].empty()) continue;
            flag = false;
            queue<state> q;
            memset(visited, 0, sizeof(visited));
            for (j = 0; j < v[i].size(); j++) {
                q.push({v[i][j].first, v[i][j].second, 0});
                visited[v[i][j].first][v[i][j].second] = true;
            }
            v[i].clear();
            while (!q.empty()) {
                state cur = q.front();
                q.pop();
                for (j = 0; j < 4; j++) {
                    int y = cur.y + dy[j];
                    int x = cur.x + dx[j];
                    if (y < 0 || x < 0 || y >= n || x >= m) continue;
                    if (cur.turn + 1 <= s[i] && visited[y][x] == false &&
                        a[y][x] == '.') {
                        q.push({y, x, cur.turn + 1});
                        v[i].push_back({y, x});
                        visited[y][x] = true;
                        a[y][x] = '1' + i;
                    }
                }
            }
        }
        if (flag) break;
    }
    int ans[10] = {0};
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if ('1' <= a[i][j] && a[i][j] <= '9') {
                ans[a[i][j] - '1']++;
            }
        }
    }
    for (i = 0; i < p; i++) cout << ans[i] << " ";
    return 0;
}