BOJ 16234 (인구 이동)

• 문제
  N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
  
  오늘부터 인구 이동이 시작되는 날이다.
  
  인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
  

  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
    
    
  • 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
    
    
  • 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
    
    
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
    
    
  • 연합을 해체하고, 모든 국경선을 닫는다.
    
    

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

• 입력
  첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
  
  둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
  
  인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
  
  
• 출력
  인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

#include<iostream>
#include<queue>
#include<cstring>

#define MAX 51
using namespace std;
int N, minimum, maximum;
int area[MAX][MAX];
bool checked[MAX][MAX];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int answer, population;
bool unionFlag = true;
queue<pair<int, int>> q;

void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> N >> minimum >> maximum;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> area[i][j];
		}
	}
}

void bfs(int y, int x) {
	queue<pair<int, int>> visited;
	population = area[y][x];
	q.push({ y,x });
	visited.push({ y,x });
	checked[y][x] = true;

	while (!q.empty()) {
		int currentY = q.front().first;
		int currentX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int newY = currentY + dy[i];
			int newX = currentX + dx[i];

			if (newY < 0 || newY >= N || newX < 0 || newX >= N || checked[newY][newX]) {
				continue;
			}
			int diff = abs(area[currentY][currentX] - area[newY][newX]);
			if (diff >= minimum && diff <= maximum) {
				q.push({ newY,newX });
				visited.push({ newY,newX });
				checked[newY][newX] = true;
				population += area[newY][newX];
				unionFlag = true;
			}
		}
	}

	int avg = population / visited.size();
	while (!visited.empty()) {
		area[visited.front().first][visited.front().second] = avg;
		visited.pop();
	}
}

int main() {
	fast_io();
	input();

	while (unionFlag) {
		unionFlag = false;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (!checked[i][j])
				{
					bfs(i, j);
				}
			}
		}
		memset(checked, false, sizeof(checked));
		answer++;
	}
	cout << answer - 1;
	return 0;
}

   삼성 코테 기출 문제로 BFS(DFS) + 시뮬레이션 문제이다. 삼성계열을 준비한다면 시뮬레이션 문제를 많이 풀어봐야할 것 같다.

인구 이동을 어떻게 시키느냐에서 막혀서 다른 분들의 풀이를 참고했다. queue 나 vector를 bfs를 위한 것 외에 하나 더 두어 경계가 풀려 인구가 포함된 나라를 체크하고 그 나라에 인구를 뿌려주는 방법이 가장 간단해 보였다 (bfs 가 끝난 다음 인구 배분)

main 함수에서도 union 확인을 위한 Flag를 설정 후 bfs 탐색을 진행한다.
(입력이 50까지라 충분히 돌아가도록 문제를 만든 것 같다)

맨 처음 unionFlag를 true로 초기화해서 while문에 들어간 횟수를 1회 차감시켜주면 된다.

나중에 스스로 꼭 다시 풀어봐야겠다.

시간 복잡도 : O(N^4)

숏코딩 => DFS를 활용한 풀이

#include<bits/stdc++.h>
using namespace std;
int n, l, r, a[54][54], vis[54][54], day;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
vector<pair<int,int>> v;
bool check(int a, int b){
	return l <=abs(a-b) && abs(a-b)<=r;
}
int dfs(int y, int x){
	vis[y][x]=1;
	v.push_back({y,x});
	int sum = a[y][x];
	for(int i=0;i<4;i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(nx <0 || ny <0 || nx >= n || ny >= n||vis[ny][nx])continue;
		if(check(a[y][x], a[ny][nx])){
			sum += dfs(ny, nx);
		}
	}
	return sum;
}
int main(){
	cin >> n >> l >> r;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)cin >> a[i][j];
	}
	
	while(true){
		
		bool flag = false;
		memset(vis, 0, sizeof(vis));
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(!vis[i][j]){
					v.clear();
					int sum = dfs(i,j);
					if(v.size()==1)continue;
					for(auto it : v){
						a[it.first][it.second]=sum/v.size();
						flag = true;
					}
				}
			}
		}
		if(!flag)break;
		day++;
	}
	cout << day <<"\n";
	return 0;
}

   여기서도 vector를 하나 두어 인구 분배에 들어갈 영토를 기록해두고 뿌린다.