이번에는 백준 16234번 인구 이동 문제를 풀어보았습니다.
문제를 처음 봤을 때 국경이 열리는 나라들끼리 하나의 그룹으로 묶인다는 점에서 연결된 컴포넌트를 찾는 문제라고 생각했습니다.
그래서 DFS를 이용하여 연합을 이루는 나라들을 찾고, 해당 연합의 인구를 재분배하는 과정을 반복하도록 구현하였습니다.
문제 설명
인접한 두 나라의 인구 차이가 L명 이상 R명 이하라면 국경을 열 수 있습니다.
국경이 열린 나라들은 하나의 연합을 이루게 되며, 연합에 속한 나라들의 인구는 연합 전체 인구를 나라 수로 나눈 값으로 변경됩니다.
더 이상 인구 이동이 발생하지 않을 때까지 이 과정을 반복할 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제입니다.
풀이 아이디어
DFS를 이용하여 인구 이동이 가능한 나라들을 하나의 컴포넌트로 묶었습니다.
방문한 나라에는 같은 번호를 부여하여 같은 연합임을 표시하였습니다.
모든 연합을 찾은 뒤에는 연합에 속한 나라들의 좌표를 모아서 인구 수를 계산하였습니다.
계산된 평균 인구 수를 다시 연합에 속한 모든 나라에 적용하였습니다.
이 과정을 반복하면서 더 이상 새로운 연합이 생성되지 않는 경우 반복을 종료하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> country_map;
vector<vector<int>> visited;
vector<vector<pair<int, int>>> connected_country;
vector<int> avg_people_cnt;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
int N,L,R;
void dfs(int y, int x, int comp_num, bool &found) {
visited[y][x] = comp_num;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && nx >= 0 && ny < N && nx < N) {
int diff = abs(country_map[ny][nx] - country_map[y][x]);
if (visited[ny][nx] == 0 && diff >= L && diff <= R) {
found = true;
dfs(ny, nx, comp_num, found);
}
}
}
if (found == false) {
visited[y][x] = 0;
}
}
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++) {
country_map.push_back(vector<int>());
visited.push_back(vector<int>());
for (int j=0; j<N; j++) {
int temp;
cin >> temp;
country_map[i].push_back(temp);
visited[i].push_back(0);
}
}
int day_cnt = 0;
while(true) {
bool not_present = true;
int comp_num = 1;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (visited[i][j] == 0) {
bool found = false;
dfs(i, j, comp_num, found);
if (found) {
comp_num++;
not_present = false;
}
}
}
}
if (not_present) break;
for (int cpn=1; cpn<=comp_num; cpn++) {
connected_country.push_back(vector<pair<int, int>>());
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (visited[i][j] == cpn) {
connected_country[cpn-1].push_back({i,j});
}
}
}
}
for (vector<pair<int,int>> comp : connected_country) {
int people_cnt = 0;
for (pair<int, int> p : comp) {
people_cnt += country_map[p.first][p.second];
}
people_cnt = people_cnt / comp.size();
for (pair<int, int> p : comp) {
country_map[p.first][p.second] = people_cnt;
}
}
connected_country.clear();
fill(visited.begin(), visited.end(), vector<int>(N,0));
day_cnt++;
}
cout << day_cnt << endl;
return 0;
}풀이 흐름
- 입력을 받아 각 나라의 인구 수를 저장합니다.
- DFS를 이용하여 인구 이동이 가능한 나라들을 같은 컴포넌트 번호로 묶습니다.
- 모든 나라를 탐색한 뒤 생성된 컴포넌트들을 확인합니다.
- 각 컴포넌트에 속한 나라들의 좌표를 저장합니다.
- 연합의 전체 인구 수를 계산한 뒤 나라 수로 나누어 평균 인구를 구합니다.
- 연합에 속한 모든 나라의 인구를 평균값으로 변경합니다.
- 인구 이동이 발생한 경우 하루를 증가시키고 다시 탐색합니다.
- 더 이상 연합이 생성되지 않으면 반복을 종료합니다.
구현 포인트
1. DFS를 이용한 연합 찾기
인접한 나라의 인구 차이가 조건을 만족하면 같은 컴포넌트로 묶었습니다.
if (visited[ny][nx] == 0 && diff >= L && diff <= R) {
found = true;
dfs(ny, nx, comp_num, found);
}조건을 만족하는 나라들을 계속 탐색하면서 같은 번호를 부여하였습니다.
2. 방문 배열에 컴포넌트 번호 저장
단순 방문 여부가 아니라 연합 번호를 저장하도록 구현하였습니다.
visited[y][x] = comp_num;같은 번호를 가진 나라들은 같은 연합에 속한 나라들입니다.
3. 연합이 없는 경우 처리
현재 나라에서 연결된 다른 나라를 찾지 못한 경우에는 다시 0으로 변경하였습니다.
if (found == false) {
visited[y][x] = 0;
}혼자만 존재하는 나라는 연합으로 취급하지 않도록 하였습니다.
4. 연합별 나라 좌표 저장
DFS가 끝난 뒤에는 같은 컴포넌트 번호를 가진 나라들을 모아 저장하였습니다.
if (visited[i][j] == cpn) {
connected_country[cpn-1].push_back({i,j});
}이후 인구 계산은 저장된 좌표를 이용하여 진행하였습니다.
5. 연합 인구 재분배
연합에 속한 나라들의 인구를 모두 더한 뒤 평균을 계산하였습니다.
people_cnt = people_cnt / comp.size();계산된 평균 인구를 연합에 속한 모든 나라에 적용하였습니다.
country_map[p.first][p.second] = people_cnt;6. 인구 이동 반복
하루 동안의 인구 이동이 끝나면 방문 배열과 연합 정보를 초기화하였습니다.
connected_country.clear();
fill(visited.begin(), visited.end(), vector<int>(N,0));이후 다시 DFS를 수행하여 새로운 연합이 있는지 확인하였습니다.
7. 더 이상 연합이 없으면 종료
인구 이동이 가능한 연합을 하나도 찾지 못한 경우 반복을 종료하였습니다.
if (not_present) break;이때까지 발생한 인구 이동 횟수가 정답이 됩니다.
