[백준 16234번 C/C++] 인구 이동

 

[백준 16234번 C/C++] 인구 이동

 

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

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

---

 

해결전략

 

너비 우선 탐색 BFS

 

---

 

코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int dy[4] = {-1, 1, 0, 0}; // 선언: 상, 하 이동
const int dx[4] = {0, 0, -1, 1}; // 선언: 좌, 우 이동
 
int n, l, r; // 선언: n - 격자 크기, l - 최소 인구 차이, r - 최대 인구 차이
int a[50][50]; // 선언: 각 나라의 인구 수 행렬
bool visit[50][50]; // 선언: 각 나라의 방문 여부 행렬
 
vector<pair<int, int>> open; // 선언: 연합국 위치 저장
 
// bfs 함수: 인구 이동이 가능한 인접한 나라를 찾는 함수
bool bfs(int y, int x) {
    if (visit[y][x]) return false; // 이미 방문한 나라라면 false 반환
 
    open.clear(); // 연합국 위치 저장 벡터 초기화
    queue<pair<int, int>> q; // 선언: 연합국 위치 저장 큐
    q.push(make_pair(y, x)); // 해당 위치를 큐에 추가
    visit[y][x] = true; // 그 위치를 방문 표시
    open.push_back(make_pair(y, x)); // 연합국 위치 저장 벡터에 추가
 
    while (!q.empty()) { // 큐가 빌 때까지 반복
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
 
        for (int dir = 0; dir < 4; ++dir) { // 상, 하, 좌, 우 방향 범위
            int ny = cy + dy[dir]; // 새로운 y 위치 계산
            int nx = cx + dx[dir]; // 새로운 x 위치 계산
 
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue; // 격자 밖에 있다면 다음 방향 확인
            if (visit[ny][nx]) continue; // 이미 방문한 경우 다음 방향 확인
 
            int diff = abs(a[ny][nx] - a[cy][cx]); // 인접한 나라의 인구 차이 계산
            if (l <= diff && diff <= r) { // 인구 차이가 l 이상 r 이하일 경우
                q.push(make_pair(ny, nx)); // 큐에 위치 저장
                visit[ny][nx] = true; // 방문 표시
                open.push_back(make_pair(ny, nx)); // 연합국 위치 저장 벡터에 추가
            }
        }
    }
 
    return open.size() > 1; // 연합국이 2개 이상이면 true 반환, 아니면 false 반환
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> l >> r; // 입력: n, l, r
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j]; // 입력: 각 나라의 인구 수 행렬 a
        }
    }
 
    int ans = 0; // 선언 및 초기화: 인구 이동이 발생한 총 라운드 수
    while (true) { // 인구 이동이 더 이상 발생하지 않을 때까지 반복
        memset(visit, false, sizeof(visit)); // 방문 배열 초기화
        bool flag = false; // 선언 및 초기화: 이동 여부 플래그
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (bfs(i, j)) { // 해당 위치에서 bfs 실행 후 연합국이 2개 이상일 경우
                    flag = true;   // 이동 여부 플래그 true로 설정
 
                    int sum = 0; // 선언 및 초기화: 연합국 인구 수 총합
                    for (auto& p : open) {
                        sum += a[p.first][p.second]; // 연합국 인구 수 누적
                    }
                    int avg = sum / open.size(); // 연합국 인구 평균
 
                    for (auto& p : open) {
                        a[p.first][p.second] = avg; // 연합국별로 새로운 인구 수 할당
                    }
                }
            }
        }
        if (!flag) break; // 이동이 발생하지 않은 경우 라운드 종료
        ans++; // 인구 이동이 발생한 경우 라운드 수 증가
    }
 
    cout << ans << '\n'; // 결과 출력: 인구 이동이 발생한 총 라운드 수
 
    return 0;
}

 

 

---