백준 [16234] 인구이동

삼성 SW역량테스트 문제이다.

링크 : https://www.acmicpc.net/problem/16234

BFS를 통한 4방향탐색을 진행하면서 문제의 조건에 맞게끔 국경선을 열어 인구이동을 진행하여 각 칸의 인구수를 갱신시켜준다.

유의할점은 BFS를 한번진행하고 끝날 때, 인구수를 갱신시켜주면 Time Limit가 발생한다.

처음 모든 칸에 대한 인구이동이 일어난 후 모든칸에 대해 인구수를 갱신시켜야 Time Limit를 피할 수 있다. 이를 위해 한 영역에 대한 나라수와 총합을 저장하는 변수가 필요하다. 

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
using namespace std;
 
int n, l, r, arr[55][55], dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 },ans;
 
int main()
{
    cin >> n >> l >> r;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &arr[i][j]);
        }
    }
    while (1) {
        int visit[55][55] = { 0 };
        int num = 0,chk=0,cnt=0;
        int cal[2510][2] = { 0 };
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] == 0) {
                    cnt++;
                    
                    queue<pair<int, int>> q;
                    q.push({ i,j });
                    visit[i][j] = cnt;
                    while (!q.empty()) {
                        int x, y;
                        x = q.front().first;
                        y = q.front().second;
                        cal[cnt][0]++;
                        cal[cnt][1] = cal[cnt][1] + arr[x][y];
                        q.pop();
                        for (int z = 0; z < 4; z++) {
                            int kx, ky,dis=0;
                            kx = x + dx[z];
                            ky = y + dy[z];
                            if (kx < 0 || kx >= n || ky < 0 || ky >= n || visit[kx][ky] != 0) continue;
                            dis = abs(arr[x][y] - arr[kx][ky]);
                            if (dis >= l && dis <= r) {
                                chk = 1;
                                q.push({ kx,ky });
                                visit[kx][ky] = cnt;
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visit[i][j] != 0) {
                    arr[i][j] = cal[visit[i][j]][1] / cal[visit[i][j]][0];
                }
            }
        }
        if (chk == 0) break;
        ans++;
    }
    printf("%d", ans);
    return 0;
}