[Algorithm] Baekjoon 16234번 : 인구 이동

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
struct Position
{
    int y;
    int x;
};
 
int n, l, r;
int arr[51][51] = { 0 };
bool visited[51][51] = { false };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int BFS(int sy, int sx)
{
    visited[sy][sx] = true;
 
    vector<Position> unionPositions;
    unionPositions.push_back({ sy,sx });
 
    queue<Position> q;
    q.push({ sy,sx });
    
    int sumPopulation = arr[sy][sx];
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
            
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == n) continue;
            if (visited[nextY][nextX]) continue;
 
            int gap = abs(arr[nextY][nextX] - arr[curY][curX]);
            if (gap >= l && gap <= r)
            {
                visited[nextY][nextX] = true;
                sumPopulation += arr[nextY][nextX];
                unionPositions.push_back({ nextY,nextX });
                q.push({ nextY,nextX });
            }
        }
    }
 
    int unionCount = unionPositions.size();
 
    if (unionCount == 1) return 0;
 
    int num = sumPopulation / unionCount;
    
    for (int i = 0; i < unionPositions.size(); ++i)
    {
        int y = unionPositions[i].y;
        int x = unionPositions[i].x;
 
        arr[y][x] = num;
    }
 
    return unionCount;
}
 
bool Move()
{
    int moveCount = 0;
    memset(visited, false, sizeof(visited));
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (visited[i][j]) continue;
 
            int count = BFS(i, j);
            if (count > 1) ++moveCount;
        }
    }
 
    return moveCount == 0 ? false : true;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> l >> r;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    int answer = 0;
 
    while (1)
    {
        if (!Move()) break;
        ++answer;
    }
    
    cout << answer;
}
 
 

 

간만에 풀어보는 그래프 + 시뮬레이션 문제.

어려운 난이도는 아닌데, 단계가 있다보니 살짝 헷갈렸다.

처음엔 인구이동을 먼저 전부 시킨 후에, 각 그룹마다 평균값을 대입시켰는데 통과는 했다만 시간이 생각보다 너무 나와서 다시 풀어봤다.

 

생각해보니 인구이동연합을 한덩어리 구한다음에 바로 거기다가 평균값 넣어도, 방문체크를 다 해놨으면 다른쪽에서 탐색했을 때 영향을 안끼치게 할 수 있단걸 알아서 시간을 반으로 줄이긴 했다.