BOJ

BOJ::16920 확장 게임

BOJ Gold 2

BOJ::16920 확장 게임

시사점

시행착오

  • 문제에는 벽이 주어집니다.
    • 즉, 남은 빈칸이 존재하더라도 해당 칸이 벽에 둘러쌓여있으면 정복할 수 없습니다.
  • 처음엔 단순하게, 각 그룹의 인원들을 저장하는 vector를 생성하여 사용하였습니다.
    • 그리고, 해당 플레이어의 차례가 되면 모든 인원을 queue에 넣어주는 작업을 진행하였습니다.
    • 시간초과를 받습니다.
  • queue[grpMax]를 생성하여, 각 그룹별로 queue를 할당받습니다.
    • 이때 queue의 원소는 {x,y,dist}를 사용했습니다.
    • 또한, dist+1의 값이 해당 플레이어가 갈 수 있는 거리보다 먼 경우 nextQ라는 곳에 push해 주었습니다.
    • 그리고, queue가 빌때까지 실행한 후, nextQ에서 해당 큐로 옮겨담습니다.
    • 이러한 일련의 작업은 dist를 관리하기 매우 힘들게 만듦니다.
    • 즉, nextQ에서 옮겨담은 경우, pop한 값 자체에 대해서 방문처리를 해주어야 합니다.
    • 또한, pop한 값 자체가 이미 다른 플레이어에 의해 방문처리 되어있는 경우도 발생합니다.
    • 여기서 꽤 오랜 시간을 소모했습니다.
    • 하지만, 결국 제대로 dist를 관리하지 못하였고 계속해서 메모리초과를 받았습니다.
  • 생각해보니, 굳이 새로운 queue에 옮겨담을 필요도, {x,y,dist}를 push할 필요도 없었습니다.
  • {x,y}만 push하면 됩니다.
  • 그리고, dist를 mxDist가 될때까지 while문을 돌려주면 되지요..
  • 이렇게 되면 자동으로, 현재 정점에서 갈 수 있는 최대한의 정점을 방문한 상태가 되고, 갈 수 없는 바로 다음 정점은 큐에 자연스럽게 들어가게 됩니다.
  • Si값이 10^9까지 주어질 수 있습니다.

키

이해(x)

설계, 손 코딩(x)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(x)

함수 List

업데이트 되는 변수

실제 구현

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define INF 987654321
const int MAXNM = 1000, MAXGRP = 9;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
struct cell{int x; int y;};
using namespace std;

int n, m, p, total, counted;
char a[MAXNM][MAXNM];
int Si[MAXGRP];
int grpSize[MAXGRP];
queue<cell> qGrp[MAXGRP];
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=m);}

bool bfs(int colur, int mxdist){
    bool ret = false;
    while(mxdist--){
        int sz = (int) qGrp[colur].size();
        while(sz--){
            int x = qGrp[colur].front().x, y = qGrp[colur].front().y;
            qGrp[colur].pop();

            if(a[x][y] == '.'){ // nextQ에 의해서 들어온 경우
                ret = true;
                grpSize[colur]++;
                a[x][y] = colur + '1';
                counted++;
            }
            if(a[x][y] != colur+'1') continue;
            rep(i, 0, 4){
                int nx = x+dx[i], ny = y+dy[i];
                if(over(nx, ny) || a[nx][ny] != '.') continue;
                ret = true;
                qGrp[colur].push({nx, ny});
                grpSize[colur]++;
                a[nx][ny] = colur + '1';
                counted++;
            }
        }
    }
    return ret;
}

void solve(){
    while(counted < total){
        bool able = false;
        rep(i, 0, p){
            if(bfs(i, Si[i])){
                able = true;
            }
        }
        if(able == false) break;
    }
    rep(i, 0, p)cout << grpSize[i] << " ";
    cout << '\n';
}
int main(){
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> p;
    rep(i, 0, p){
        cin >> Si[i];
        if(Si[i] > n *m) Si[i] = n *m;
    }
    rep(i, 0, n) rep(j, 0, m){
        cin >> a[i][j];
        if(a[i][j] != '#') total++;
        if(a[i][j] >='1' && a[i][j] <='9'){
            qGrp[a[i][j]-'1'].push({i, j});
            grpSize[a[i][j]-'1']++;
            counted++;
        }
    }
    solve();
    return 0;
}

구현 후 코드리뷰 + 예제 돌려보기(x)

디버깅(x)

좋은 코드

최적화