오늘 풀어본 문제는 백준 16234 인구이동문제이다!
tony9402 님의 문제집 중 시뮬레이션으로 분류되어 있는 문제중 추천문제를 골라 풀어보았다!
BOJ 16234 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
입출력
나의 풀이
주어진 입력의 지도에서 연합이 가능한 지역을 탐색하고 연합에 포함된 나라들의 인구를 재조정하는 과정을, 지도에서 연합이 존재하지 않을 때 까지 반복해야 하는 시뮬레이션 문제이다.
처음엔 지도의 (0,0) 에서 시작해서 BFS를 이용해 연합 가능 지역을 찾은 뒤 인구 이동을 시작했지만 지도에 독립된 연합이 복수개 존재할 수 있기 때문에 연합 지역 탐색 과정과 인구 이동 과정이 완전히 분리되어야 한다는 걸 알게 되었다!
[연합 지역 탐색] & [인구 이동] 과정을 반복하되, 연합 지역 탐색 결과 발견한 연합 지역이 없다면 반복을 멈추고 인구 이동 횟수를 반환하였다.
연합 지역 탐색 과정에서 좌우상하로 연합이 가능한 국가가 존재하는 좌표를 기준으로 BFS를 시작한다. 통합 가능한 나라들의 좌표들을 찾으며 해당 국가들의 인구 수를 더해가고, 좌표들은 vector<pair<int, int>> 로 저장해 둔다.
한번의 BFS가 끝날 때 마다 하나의 연합 지역을 찾은 것이고, 이 과정을 (0,0) 에서 (N-1, N-1) 까지 반복한다.
이 때, 모든 국가들이 단 한번만 탐색 되어야 한다! 연합에 포함되는 국가 좌표가 좌우상하 중 어떤 방향에서 먼저 탐색될지 알 수 없기 때문에 visited 배열을 이용해서 모든 좌표는 한번씩만 탐색되도록 보장했다!
전체 반복문에서 while(true) 를 사용한 것이 맘에 들지 않지만, 다른 분들의 풀이에서도 대부분 이를 많이 사용하신 것 같다 ㅜ 다른 방법을 좀 더 찾아보아야겠다!
코드
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>
// BOJ 16234 인구이동, 시뮬레이션
using namespace std;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
// 지도상에 존재하는 연합 - 연합에 포함되는 국가들 좌표와 인구 합
typedef struct unite{
int totalPopulation;
vector<pair<int, int>> countries;
unite() {
totalPopulation = 0;
countries = vector<pair<int, int>>();
}
}Unite;
// 지도상에 위치하는 연합 구하기
Unite bfs(vector<vector<int>> map, vector<vector<bool>> & visited, int i, int j, int N, int L, int R){
Unite unite;
queue<pair<int, int>> q;
// BFS 시작점 저장
q.push(make_pair(i, j));
visited[i][j] = true;
while (!q.empty()){
pair<int, int> location = q.front();
q.pop();
// 각 국가의 인구 수 누적 & 좌표 저장
unite.totalPopulation += map[location.first][location.second];
unite.countries.push_back(location);
for (int k = 0; k < 4; ++k) {
int r = location.first + dy[k];
int c = location.second + dx[k];
if (r>=0 && r<N && c>=0 && c<N){ // 지도 범위 내
int diff = abs(map[location.first][location.second] - map[r][c]); // 인구 차이
if (diff >= L && diff <= R && !visited[r][c]){ // 조건에 맞으면 연합으로, 모든 좌표 한번씩만 방문
q.push(make_pair(r, c));
visited[r][c] = true;
}
}
}
}
return unite;
}
int getMovigDays(vector<vector<int>> map, int N, int L, int R) {
int moved = 0;
while (true) {
vector<Unite> unites;
vector<vector<bool>> visited(N, vector<bool>(N, false));
// 연합 지역을 탐색
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < 4; ++k) {
int r = i + dy[k];
int c = j + dx[k];
if (r >= 0 && r < N && c >= 0 && c < N && !visited[r][c]) { // 지도 범위 내
int diff = abs(map[i][j] - map[r][c]);
if (diff >= L && diff <= R) { //시작 지점 발견하면 BFS 시작
Unite unite = bfs(map, visited, i, j, N, L, R);
unites.push_back(unite); // 연합들을 알아낸 뒤
}
}
}
}
}
// 연합이 존재 하면 인구 이동 시작
if (unites.size() > 0) {
moved++;
for (int i = 0; i < unites.size(); ++i) {
int avg = unites[i].totalPopulation / unites[i].countries.size();
for (int j = 0; j < unites[i].countries.size(); ++j) {
pair<int, int> c = unites[i].countries[j];
map[c.first][c.second] = avg;
}
}
} else {
break;
}
}
return moved;
}
int main() {
int N, L, R;
cin>>N>>L>>R;
vector<vector<int>> map(N, vector<int>(N,0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin>>map[i][j];
}
}
int answer = getMovigDays(map, N, L, R);
cout<<answer;
return 0;
}