BOJ 백준 16234 인구이동<BFS>

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

< 인구 이동 >

이 문제는 상하좌우로 인접한 국가끼리의 인구 차이가 문제에서 입력되는 L 이상, R 이하인 경우 국경이 개방되고

국경이 개방된 국가끼리 인구수를 모두 더한 후 국가 수로 나누어 평균을 내 연합된 국가에 할당해주는 문제이다.

1. bfs를 통해 연합 가능한 국가들을 찾아가면서 방문 여부를 표시해주고, 총 인구수와 총 국가 수를 갱신해나간다.

2. for문을 통해 N x N 만큼 돌면서 연합국가들의 인구수들을 갱신해 주었다면, 방문 여부를 모두 지워준다.

3. 다시 N x N 만큼 돌면서 bfs를 돌려주는데, 만약 연합 가능한 국가가 한 개도 없다면, 즉 인구 이동이 불가능하다면 반복문을 끝낸다.

다른 맞은 사람들의 효율정도를 보면 나의 부족함을 많이 느낀다. 또한 도중에 메모리초과가 났는데, 

방문했던 국가를 queue가 아닌 Vector를 통해 저장했고 이를 전역변수화 하니 메모리초과를 해결할 수 있었다.

#include <iostream>
#include <queue>
#include <vector>
#define SIZE 51
 
using namespace std;
 
int arr[SIZE][SIZE];
bool visit[SIZE][SIZE];
 
 
// 연합된 국가들을 저장할 벡터 
vector< pair<int, int> > nations;
 
int n, l, r, totalMove = 0;
 
// 국가의 상하좌우를 체크할 배열
int xarr[4] = { 1,-1,0,0 };
int yarr[4] = { 0,0,1,-1 };
 
// 인구 이동이 끝난 것을 확인할 플래그
bool moveFlag = true;
 
bool IsOpenBorder(pair<int, int> &country, int near_x, int near_y)
{
    // 존재하지 않은 국가인 경우 
    if (near_x < 0 || near_x >= n || near_y < 0 || near_y >= n) return false;
 
    // 국가 간 인구수 차이 
    int diff = (arr[country.first][country.second] - arr[near_x][near_y]);
 
    diff = diff < 0 ? diff * (-1) : diff;
 
    // 국가 간 인구수 차이가 기준에 맞지 않는 경우 
    if (l > diff || r < diff) return false;
 
    return true;
}
 
void BFS(int sx, int sy)
{
    queue< pair<int, int> > q;
 
    // 연합의 시작점을 큐에 넣기 
    q.push({ sx, sy });
    nations.push_back({ sx, sy });
    // 연합의 총 인구수를 저장할 변수 
    int totalPeople = arr[sx][sy];
    int totalNation = 1;
 
    while (!q.empty())
    {
        // 국가 하나 뽑아오기 
        pair<int, int> country = q.front();
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            // 인접한 국가의 좌표 
            int near_x = country.first + xarr[i];
            int near_y = country.second + yarr[i];
 
            // 국가 개방 여부 
            if (!IsOpenBorder(country, near_x, near_y)) continue;
            // 이미 연합된 국가라면 
            if (visit[near_x][near_y]) continue;
 
            // 국가 개방이 된 경우 큐에 넣어주기 
            q.push({ near_x, near_y });
            nations.push_back({ near_x, near_y });
            visit[near_x][near_y] = true;
            // 총 인구수 갱신 
            totalPeople += arr[near_x][near_y];
            // 총 국가 수 갱신 
            totalNation++;
        }
    }
    // 연합 국가가 없는 경우 
    if (totalNation == 1)
    {
 
        return;
    }
 
    // 평균 인구수 
    int avgPeople = totalPeople / totalNation;
 
    // 국가들에 평균 인구수 할당 
    for (int i = 0; i < nations.size(); ++i)
    {
        arr[nations[i].first][nations[i].second] = avgPeople;
    }
 
    moveFlag = true;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> l >> r;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
    // 국가가 2개 이상인 경우에만 고려 
    if (n > 1)
    {
        while (moveFlag)
        {
            moveFlag = false;
 
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    // 방문한 적이 없는 경우에만 bfs
                    if (!visit[i][j])
                    {
                        visit[i][j] = true;
                        BFS(i, j);
 
                        // vector 초기화
                        nations.clear();
                    }
                }
            }
 
            // 이동이 없었을 시 반복문 탈출 
            if (!moveFlag) break;
 
            // 이동이 있었던 경우, totalMove를 1 증가 
            ++totalMove;
            // visit 초기화 
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    visit[i][j] = false;
                }
            }
        }
    }
 
    cout << totalMove << '\n';
 
    return 0;
}