[백준 16234] 인구이동 (BFS) (C/C++) (★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
 
int map[110][110];
int N, L, R;
 
queue<pair<int, int>> q;
int visited[110][110];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < N && y >= 0 && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            visited[i][j] = 0;
        }
    }    
}
 
int check()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(visited[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
void BFS(int x, int y)
{
    // 시간초과의 원인
    // int check[110][110] = {0};
    vector<pair<int, int>> check;
    
    q.push({x, y});
    
    int sum = 0;
    int cnt = 0;
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && L <= abs(map[xpos][ypos]-map[x][y]) && abs(map[xpos][ypos]-map[x][y]) <= R)
            {
                if(visited[x][y] == 0)
                {
                    // 시간초과의 원인
                    // check[x][y] = 1;
                    check.push_back({x, y});
                    
                    visited[x][y] = 1;
                    
                    sum += map[x][y];
                    cnt++;
                }
                
                if(visited[xpos][ypos] == 0)
                {
                    // 시간초과의 원인 
                    // check[xpos][ypos] = 1;
                    check.push_back({xpos, ypos});
                    
                    visited[xpos][ypos] = 1;
                    q.push({xpos, ypos});
                    
                    sum += map[xpos][ypos];
                    cnt++;
                }
            }
        }
    }
    
    // 시간초과의 원인 
    /*
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(check[i][j] == 1)
            {
                map[i][j] = sum/cnt;
            }
        }
    }
    */
    
    // 이동 후 초기화 
    for(int i = 0; i < check.size(); i++)
    {
        map[check[i].first][check[i].second] = sum/cnt;
    }
}
 
int main(void)
{
//    freopen("B16234_input.txt", "r", stdin);
    
    scanf("%d %d %d", &N, &L, &R);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    int ans = 0;
    while(1)
    {
//        init();
        memset(visited, 0 ,sizeof(visited));
        
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                if(visited[i][j] == 0)
                {
                    BFS(i, j);    
                }
            }
        }    
        
        if(check() == 1)
        {
            printf("%d", ans);
            break;
        }
        
        ans++;
    }
    
    return 0;
}