[백준] 16234번 인구 이동

16234번 인구 이동

---

1. 이해하기

• 모든 나라의 크기는 1x1이고, 각 나라의 인구수는 맵에 나와있는 숫자이다.
• 각 나라에 인접한 나라 사이에는 국경선이 존재한다.
• 인구 이동이 시작되는 방법
  • 국경선을 공유하는 두 나라의 인구 차이가 L이상, R 이하이면, 국경선을 하루동안 연다.
  • 국경선이 모두 열렸다면, 인구 이동을 시작한다.
  • 국경선이 열려있는 나라는 연합이라 부른다.
  • 연합을 이룬 나라들의 인구수는 (연합의 인구수)/(연합을 이루고 있는 칸의 캐수)가 된다. 소수점은 버린다.
  • 연합을 해체하고, 모든 국경선을 닫는다.
• 인구 이동이 몇 번 발생하는지 알아낸다.
• 시뮬레이션 문제이다.

---

2. 구현하기

• 인접한 국가와의 인구수 차이가 L 이상, R 이하인지 살펴보고 맞으면 연합으로 포함한다.

  • bfs를 이용하여 구한다.

  vector<Point> bfs(int r, int c) {
      queue<Point> q;
      q.push({r,c});
      visited[r][c] = true;
      vector<Point> uni;
      uni.push_back({r,c});
      while(!q.empty()) {
          int x = q.front().x, y = q.front().y; q.pop();
          for(int i = 0; i < 4; i++) {
              int nx = x+dx[i], ny = y+dy[i];
              if(nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny]) continue;
              int dif = abs(map[x][y]-map[nx][ny]);
              if(L <= dif and dif <= R) {
                  q.push({nx,ny});
                  visited[nx][ny] = true;
                  uni.push_back({nx,ny});
              }
          }
      }
      return uni;
  }

• 구한 연합을 가지고 연합의 인구수를 구해, 각 나라들을 연합의 인구수로 바꿔준다.

  void inte_union(vector<Point> uni) {
      int sum = 0;
      int size = uni.size();
      for(int i = 0; i < size; i++) {
          Point now = uni[i];
          sum += map[now.x][now.y];
      }
      int val = sum/size;
      for(int i = 0; i < size; i++) {
          Point now = uni[i];
          map[now.x][now.y] = val;
      }
  }

• 인구 이동이 끝난 시점은 모든 연합의 크기가 자신의 나라만을 포함할 때이므로 그점을 체크해서 끝나는 시점을 구한다.

  int simulate() {
      int ret = 0;
      while(1) {
          memset(visited,false,sizeof(visited));
          bool finish = true;
          for(int i = 0; i < N; i++) {
              for(int j = 0; j < N; j++) {
                  if(visited[i][j]) continue;
                  vector<Point> uni = bfs(i,j);
                  if(uni.size() > 1) {
                      finish = false;
                      inte_union(uni);
                  }
              }
          }
          if(finish) break;
          ret++;
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Point{
    int x,y;
};
int map[50][50];
bool visited[50][50];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,L,R;

int abs(int a) {
    return (a<0)?-a:a;
}

vector<Point> bfs(int r, int c) {
    queue<Point> q;
    q.push({r,c});
    visited[r][c] = true;
    vector<Point> uni;
    uni.push_back({r,c});
    while(!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny]) continue;
            int dif = abs(map[x][y]-map[nx][ny]);
            if(L <= dif and dif <= R) {
                q.push({nx,ny});
                visited[nx][ny] = true;
                uni.push_back({nx,ny});
            }
        }
    }
    return uni;
}

void inte_union(vector<Point> uni) {
    int sum = 0;
    int size = uni.size();
    for(int i = 0; i < size; i++) {
        Point now = uni[i];
        sum += map[now.x][now.y];
    }
    int val = sum/size;
    for(int i = 0; i < size; i++) {
        Point now = uni[i];
        map[now.x][now.y] = val;
    }
}

int simulate() {
    int ret = 0;
    while(1) {
        memset(visited,false,sizeof(visited));
        bool finish = true;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(visited[i][j]) continue;
                vector<Point> uni = bfs(i,j);
                if(uni.size() > 1) {
                    finish = false;
                    inte_union(uni);
                }
            }
        }
        if(finish) break;
        ret++;
    }
    return ret;
}

int main() {
    cin >> N >> L >> R;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }

    cout << simulate() << '\n';
    return 0;
}