16234번

16234번 - 인구 이동

어제 시험장에서 풀었던 문제고, 그때 풀었던 방식 그대로 다시 제출해봤다. 다른 문제는 약간의 시간이 필요한 노가다여서 다시 풀기 귀찮..

기본적인 토대는 BFS를 바탕으로, 큐에 들어갈때 조건을 어떤 방식으로 하느냐의 문제였다. 

그냥 while 문을 통해서 시간을 증가시켜주면서, 각 점에서 BFS를 수행한다. BFS는 구역을 나누는 용도로 사용된다. 그리고 만약 BFS 큐에 들

어가지 않는다면 이는 더이상 이동할 수 없다는 뜻이므로 break 문을 통해서 시간을 측정한다. 그리고 큐에 넣으면서 나중에 바꿔줘야 하는 

구역들의 값과 개수를 따로 저장해서 문제를 해결했다. 

실제 시험장에서는 내가 sum과 cnt 배열의 크기를 2500까지 했었는데, area 가 1부터 시작하기 때문에 최대 인덱스 2500까지 들어가게 돼

서 처음에 배열 범위 초과 오류가 발생했었다. 큰일날뻔

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, l, r;
    int map[51][51];
    cin >> n >> l >> r;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    int time = 0;
 
    while (true)
    {
        int dist[51][51] = { 0, };
        int sum[2501] = { 0, };
        int cnt[2501] = { 0, };
        bool chk = false;
        int area = 1;
        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (dist[i][j] == 0)
                {
                    dist[i][j] = area;
                    sum[area] += map[i][j];
                    cnt[area]++;
                    area++;
 
 
                    queue<pair<int, int>> q;
                    q.push({ i,j });
 
                    while (!q.empty())
                    {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
 
                        for (int d = 0; d < 4; d++)
                        {
                            int nx = x + dx[d];
                            int ny = y + dy[d];
                            if (nx >= 0 && ny >= 0 && nx < n && ny < n && dist[nx][ny] == 0 && abs(map[x][y] - map[nx][ny]) >= l && abs(map[x][y] - map[nx][ny]) <= r)
                            {
                                dist[nx][ny] = dist[x][y];
                                sum[dist[x][y]] += map[nx][ny];
                                cnt[dist[x][y]]++;
                                q.push({ nx,ny });
                                chk = true;
                            }
                        }
                    }
 
                }
            }
        }
 
 
        if (!chk)
            break;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int num = dist[i][j];
                map[i][j] = sum[num] / cnt[num];
            }
        }
 
        
 
        time++;
    }
 
    cout << time << endl;
 
 
 
    return 0;
}