[Baekjoon(백준)][16234번] 인구 이동(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "인구 이동" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

Question_1

문제 개요

N×N 크기의 땅에 각 칸에는 나라가 있고, 나라마다 인구가 주어집니다. 인접한 나라의 인구 차이가 L 이상 R 이하일 때 국경선이 열리며, 열린 국경선을 통해 인구 이동이 일어납니다. 인구 이동은 하루 동안 진행되며, 더 이상 인구 이동이 없을 때까지 반복됩니다. 이때, 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.

해결 전략

문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용합니다. 각 칸을 시작점으로 하여 BFS를 수행하며, 조건에 맞는 인접 칸을 찾아 인구 이동을 시킵니다. 모든 칸에 대해 BFS를 수행한 뒤, 국경선이 열린 나라들의 인구를 조정합니다. 이 과정을 더 이상 인구 이동이 없을 때까지 반복합니다.

코드 구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n, l, r; // 지도 크기, 인구 차이 최소값, 인구 차이 최대값
int maps[53][53]; // 나라별 인구 저장 배열
int visited[53][53]; // 방문 여부 확인 배열
int dy[] = { -1,0,1,0 }; // 상하좌우 이동을 위한 배열
int dx[] = { 0,1,0,-1 };

vector<pair<int, int>> s; // 연합을 이루는 나라들의 좌표를 저장하는 벡터
int sum = 0; // 연합 인구수 합계

// dfs 함수를 사용하여 연합을 찾음
void dfs(int y, int x, vector<pair<int, int>>& v)
{
    for (int k = 0; k < 4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        // 지도 범위 내에 있고, 아직 방문하지 않았으며, 인구 차이가 조건에 부합할 경우
        if (ny >= 0 && nx >= 0 && ny < n && nx < n && !visited[ny][nx]) {
            int amount = abs(maps[y][x] - maps[ny][nx]);
            if (amount >= l && amount <= r) {
                visited[ny][nx] = 1;
                v.push_back({ ny,nx });
                sum += maps[ny][nx];
                dfs(ny, nx, v);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maps[i][j];
        }
    }
    int ret = 0; // 인구 이동이 발생하는 날짜 수
    
    while (true) {
        bool isCounting = false;
        fill(&visited[0][0], &visited[0][0] + 53 * 53, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    s.clear();
                    visited[i][j] = 1;
                    s.push_back({ i,j });
                    sum = maps[i][j];
                    dfs(i, j, s);
                    if (s.size() > 1) {
                        for (auto& b : s) {
                            maps[b.first][b.second] = sum / s.size();
                        }
                        isCounting = true;
                    }
                }
            }
        }
        if (!isCounting) break;
        ret++;
    }
    cout << ret << "\n";
}

코드 설명

• 모든 칸에 대해 방문하지 않은 칸을 시작으로 DFS를 수행합니다.
• DFS를 통해 연합을 이루는 나라들을 찾고, 연합 인구수를 조정합니다.
• 인구 이동이 더 이상 발생하지 않을 때까지 이 과정을 반복합니다.

결론

이 문제는 BFS 또는 DFS 알고리즘을 사용하여 연합을 찾고, 인구 이동을 시키는 과정을 반복하여 해결할 수 있습니다. 이 과정을 통해 인구 이동이 며칠 동안 발생하는지 계산할 수 있습니다.