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

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

 

---

해설

인구이동 문제이다.

핵심은 인접한 마을의 인구수가 L보다 크거나 같고 R보다 작거나 같으면 이동이 가능하다고 판단하고 

인구이동을 시키는것이다.

 

Connected Component를 구하는 문제이다.

 

이동이 가능하다는 것의 판단은 인접한 두 마을 사이의 인구차이 값에 절대값을 취해서 판단해주면 된다.

문제는 n*n짜리 보드(배열)에서 '어떻게' 이동이 가능한 마을을 '묶어서' 처리하냐는 것이다.

 

본인 처음에 dfs나 bfs로 탐색하여 unoin find?나 그룹화할 또 다른 배열을 만들어서 같은 번호의 그룹끼리 

합을 더하고 평균을 내서 원본 board배열에 값을 갱신하는 아이디어를 생각했는데 이 보다 간단한 방법이 있다.

 

'묶어서' 처리한다는 부분을 조금 수정하도록 하겠다. 묶어서 처리할 필요가 없다. 그냥 dfs(bfs든)로 탐색을 해서

그때그때 인구 이동이 가능하다면 v라는 벡터에 해당 좌표를 담아두면서 합을 누적해서 구한다.

이 벡터의 사이즈가 2이상이라면 인구이동이 발생했다는 뜻이니 평균을 구해서 board 2차원 배열을 업데이트 시켜주면된다.

 

본인이 생각하는 핵심은 v라는 벡터에 CC들을 담아두는 아이디어가 핵심이라 생각이 든다. 

이 부분이 없으면 예외처리를 한다고 코드가 길어지고 조금 복잡해지는 부분들이 있는듯 하다.

 

(시간 복잡도는 n의 최대가 50이고 최대 2000번 인구 이동이 발생한다고 했기 때문에 5000000 정도이다)

 

---

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'

const int MAX = 54;
int vis[MAX][MAX], board[MAX][MAX], n, L, R, sum, cnt;
const int dr[4] = {0, 1, 0, -1}, dc[4] = {-1, 0, 1, 0};
vector<pair<int, int>> v;

void dfs(int r, int c, vector<pair<int, int>>& v)
{
	for (int d = 0; d < 4; ++d)
	{
		int nr = r + dr[d], nc = c + dc[d];
		if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
		if (vis[nr][nc]) continue;
		if (abs(board[nr][nc] - board[r][c] >= L) && abs(board[nr][nc] - board[r][c]) <= R)
		{
			vis[nr][nc] = 1; 
			v.push_back({nr, nc});
			sum += board[nr][nc];
			dfs(nr, nc, 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 >> board[i][j];
   			
	while (true) // 2000
	{
		bool flag = false;
		fill(&vis[0][0], &vis[0][0] + MAX * MAX, 0);
		
		for (int i = 0; i < n; ++i) // 2500
		{
			for (int j = 0; j < n; ++j)
			{
				if (!vis[i][j])
				{
					v.clear();
					vis[i][j] = 1;
					v.push_back({i, j});
					sum = board[i][j];
					dfs(i, j, v);
					if (v.size() == 1) continue;
					for (auto pair : v)
					{
						board[pair.first][pair.second] = sum / v.size();
						flag = 1;
					}
				}
			}
		}
		if (!flag) break;
		cnt++;
	}
	cout << cnt << endl;
}