문제 출처

1. 문제설명

  • N*N 크기의 땅이 있고, 각 칸은 1x1개의 칸으로 이루어져 있다.
  • 각각의 땅 r행 c열에는 A[r][c]명이 살고 있다.
  • 인구 이동은 하루동안 진행되고, 방법이 없을 때까지 지속된다.
    • 인접한 국경의 인구 차이가 L명 이상 R명 이하라면, 인구 이동이 가능하고 이를 연합이라 부른다.
    • 연합을 이루는 각 칸의 인구 수는 연합의 인구수 / 연합을 이루는 칸의 개수로 갱신된다.
      • 소수점은 버린다.
    • 연합을 해체하고, 국경선을 닫는다.
  • 인구 이동이 며칠 동안 발생하는지 구하라



2. 알고리즘 설계

  • BFS 기법을 이용해 연합이 만들어지는지 탐색한다.
  • 연합이 만들어진다면, 위에 언급된 계산 방식으로 칸의 인구 수를 갱신한다.
  • 연합이 만들어지지 않았다면, 종료 조건이 된다.
  • 코드에 상세한 주석을 작성하였다.



3. 전체 코드

#include <bits/stdc++.h>
#define Y first
#define X second
using namespace std;
using pii = pair<int,int>;
const int SZ = 55;
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
int n, l, r, ans;
int A[SZ][SZ];
bool vis[SZ][SZ];
bool bfs(int y, int x) {
    int sum = 0;
    vector<pii> ret;  // 갱신해야 할 칸의 위치
    queue<pii> q;  // BFS 탐색용 큐
    // 큐와 벡터에 시작점을 넣는다.
    // sum에도 시작점의 값을 더한다.
    q.push({y, x});
    ret.push_back({y, x});
    vis[y][x] = true;
    sum += A[y][x];
    while(!q.empty()) {
        pii cur = q.front();
        q.pop();
        for(int dir=0; dir<4; dir++) {
            int ny = cur.Y + dy[dir];
            int nx = cur.X + dx[dir];
            int cmp = abs(A[cur.Y][cur.X] - A[ny][nx]);
            if(ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
            if(!vis[ny][nx] && cmp >= l && cmp <= r) {
                vis[ny][nx] = true;
                q.push({ny, nx});
                // BFS의 조건을 만족할 시 벡터와 sum값을 갱신
                ret.push_back({ny, nx});
                sum += A[ny][nx];
            }
        }
    }
    // while()문 전에 시작점을 넣었기 때문에
    // 조건을 만족하는 칸이 한 개 이상이 있으면,
    // 벡터의 크기는 2 이상이 될 것이다.
    if(ret.size() > 1) {
        for(auto a : ret) // 값을 갱신시켜주고
            A[a.Y][a.X] = (sum / ret.size());
        return true;  // 값이 갱신되었음을 알린다.
    }
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> l >> r;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> A[i][j];
    
    while(true) {
        fill_n(&vis[0][0], SZ*SZ, false);
        bool flag = false;
        // 굳이 별도로 담지 않고,  그때그때 처리하는 이유는
        // 인접한 칸을 모두 처리하기 때문에 그때그때 처리해도
        // 동시에 처리하는 것과 같은 효과이다.
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                // 현재 점이 이전에 탐색되지 않았고,
                // 갱신할 점이 한개라도 있었다면,
                if(!vis[i][j] && bfs(i, j))
                    flag = true;
        if(!flag) break;
        ans++;
    }
    
    cout << ans;
    return 0;
}



4. 소감

  • 어떻게 하면 인구 이동이 없을 때까지 루프를 돌릴 수 있을까 고민했던 문제이다.
  • 종료 조건이 어느 시점이 되면 찾아오는 게 아니라, 값의 변화에 따라 찾아오기 때문에 구현법이 빠르게 떠오르지 않았다.