[ baekjoon ] #16234 인구이동

백준 #16234 인구이동

문제 요약

---

• 인구 이동 규칙
  ① L명 ≤ 국경선을 공유하는 두 나라의 인구 차이 ≤ R명 → 국경선 open
  ② 위의 조건으로 열어야하는 국경선이 모두 열렸다면 인구 이동 start
  ③ 국경선이 열려있어 이동할 수 있으면 그 나라를 하루 동안 연합이라고 한다.
  ④ 연합을 이루고 있는 각 칸의 인구수 → (연합의 인구수)/(연합을 이루고 있는 칸의 개수)
  이때, 소수점은 버린다.
  ⑤ 연합을 해체하고 모든 국경선을 닫는다.
• 인구 이동이 며칠 동안 발생하는지 구하기 !

💡Idea(DFS)

1. 국경선 open 여부를 어떻게 저장할까?
   → 방문 여부를 저장하는 visit 배열을 만들자
2. 인구 이동을 어떻게 하지?
   • 인구 이동을 하려면 연합 나라의 총 인구수, 연합 나라의 개수가 필요하다.
     → 각 연합의 인구수를 저장할 total배열과 연합 나라의 개수를 저장할 cnt배열 생성 !
3. 인구 이동 여부를 어떻게 판단할까?
   • 주변 나라를 탐색할 때 연합할 수 있을 경우 bool 변수(check)를 true로 설정 !
     → !check일 경우 break 후 day 증가

[ SourceCode ]

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

int N, L, R; // 나라 크기(N*N), 인구 차이 최소, 최대
int country[50][50], visit[50][50]; // 나라 인구수, 방문 여부
int cnt[2501], total[2501];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우

void dfs(int x, int y, int kind, queue<tuple<int, int, int>> &list, bool &check) {
    if(x < 0 || x >= N || y < 0 || y >= N) return;
    for(int i=0; i<4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if(visit[nx][ny] == 0) {
            int diff = abs(country[x][y] - country[nx][ny]); // 인구 차이
            if(diff >= L && diff <= R) {
                visit[nx][ny] = 1;
                total[kind] += country[nx][ny];
                cnt[kind]++;
                list.push(make_tuple(kind, nx, ny));
                check = true;
                dfs(nx, ny, kind, list, check);
            }
        }
    }
}

int main() {
    int day = 0; // 총 인구 이동 날짜
    cin >> N >> L >> R;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> country[i][j];
        }
    }

    while(1) {
        int kind = 0;
        bool check = false;
        queue <tuple<int, int, int>> list;
        fill(cnt, cnt + 2501, 0);
        fill(total, total + 2501, 0);
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(visit[i][j] == 0) { // 처음 방문할 때
                    visit[i][j] = 1;
                    kind++;
                    cnt[kind]++; // 나라 수
                    total[kind] += country[i][j]; // 인구 수
                    list.push(make_tuple(kind, i, j));
                    dfs(i, j, kind, list, check);
                }
            }
        }

        if(!check) {
            break;
        }

        while(!list.empty() && check) {
            int idx = get<0>(list.front());
            int x = get<1>(list.front());
            int y = get<2>(list.front());
            list.pop();
            country[x][y] = total[idx] / cnt[idx];
            visit[x][y] = 0;
        }

        day++;
    }

    cout << day;

    return 0;
}

Feedback

---

1. 최대 나라의 개수는 N=50일 경우이므로 50 * 50 = 2500개이다.
   → cnt, total 배열의 크기를 2501개로 했어야하는데 50개로 설정하여 Runtime Error가 발생하였다.