백준 16234번 - 인구 이동 (C++)

문제

해결 방법 : 시작점부터 배열을 BFS방식으로 하나의 국가로 묶어서 인구 이동을 처리하였다. -> 이후 반복.

아쉬운 점 : 시간이 너무 많이 걸렸고, 코드도 비 효율적이며, 가독성마저 구리다. 상위권은 한자릿수던데 난 700ms...

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
void Puch_Que(queue<pair<int, int>>& _Que, bool (*_bo)[51] ,int _a, int _b)
{
    if (!_bo[_a][_b])
    {
        _Que.push(make_pair(_a, _b));
        _bo[_a][_b] = true;
    }
}
 
bool ifCheck(vector<vector<int>> &Vec, queue<pair<int, int>> &Que, int a, int b, int L, int R)
{
    return (Vec[Que.front().first][Que.front().second] - Vec[Que.front().first + a][Que.front().second + b] >= L && Vec[Que.front().first][Que.front().second] - Vec[Que.front().first + a][Que.front().second + b] <= R) || (Vec[Que.front().first][Que.front().second] - Vec[Que.front().first + a][Que.front().second + b] <= -L && Vec[Que.front().first][Que.front().second] - Vec[Que.front().first + a][Que.front().second + b] >= -R);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //입력
    int N, L, R;
    cin >> N >> L >> R;
    vector<vector<int>> Vec(N);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            int a;
            cin >> a;
            Vec[i].emplace_back(a);
        }
 
    //실행
    int Count = 0;
    while (true)
    {
        bool WhileCheck = false;
        bool Check[51][51] = {}; //탐색 확인용 bool
        for (int i = 0; i < Vec.size(); ++i)
        {
            for (int j = 0; j < Vec[i].size(); ++j)
            {
                if (!Check[i][j])
                {
                    vector<pair<int, int>> SaveVec;
                    queue<pair<int, int>> Que;
                    Puch_Que(Que, Check, i, j);
                    while (!Que.empty())
                    {
                        if ((Que.front().second + 1 <= N - 1) && ifCheck(Vec, Que, 0, 1, L, R)) //우
                        {
                            Puch_Que(Que, Check, Que.front().first, Que.front().second);
                            Puch_Que(Que, Check, Que.front().first, Que.front().second + 1);
                            WhileCheck = true;
                        }
                        if ((Que.front().first - 1 >= 0) && ifCheck(Vec, Que, -1, 0, L, R)) //하
                        {
                            Puch_Que(Que, Check, Que.front().first, Que.front().second);
                            Puch_Que(Que, Check, Que.front().first - 1, Que.front().second);
                            WhileCheck = true;
                        }
                        if ((Que.front().second - 1 >= 0) && ifCheck(Vec, Que, 0, -1, L, R)) //좌
                        {
                            Puch_Que(Que, Check, Que.front().first, Que.front().second);
                            Puch_Que(Que, Check, Que.front().first, Que.front().second - 1);
                            WhileCheck = true;
                        }
                        if ((Que.front().first + 1 <= N - 1) && ifCheck(Vec, Que, 1, 0, L, R)) //상
                        {
                            Puch_Que(Que, Check, Que.front().first, Que.front().second);
                            Puch_Que(Que, Check, Que.front().first + 1, Que.front().second);
                            WhileCheck = true;
                        }
                        SaveVec.emplace_back(Que.front());
                        Que.pop();
                    }
                    int Max = 0;
                    for (auto& i : SaveVec)
                        Max += Vec[i.first][i.second];
                    for (auto& i : SaveVec)
                        Vec[i.first][i.second] = Max / SaveVec.size();
                }
            }
        }
 
        if (!WhileCheck)
            break;
        ++Count;
    }
    cout << Count;
}

잡설 : 2중for문을 좀 더 효율적으로 돌릴 순 있을 것 같은데, 속도가 200배쯤 차이나는건 이유를 잘 모르겠다. 자고일어나서 상위권 코드 한번 훑어봐야지..