백준(BOJ) 16234번 인구 이동

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

16234번: 인구 이동

풀이 :

 

연합이 될 수있는 칸들을 BFS를 통해서 탐색한다. 연합이 자기 자신을 제외하고 하나라도 있다면

 

ans를 +1 해주고 계속해서 연합을 탐색하고 아니라면 바로 종료한다.

 

연합들을 만들었다면 값들을 모두 바꾸어 주어야 하는데 스택을 이용하여 BFS를 통해 방문한 좌표들을

 

담은 후 새로 구한 값으로 다 바꾸어주자.

 

코드( C ++ )

	#include <iostream>
	#include <algorithm>
	#include <queue>
	#include <stack>
	#include <cstring>
	using namespace std;
	int n, l, r;
	int a[50][50];
	int visited[50][50];
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	bool bfs(int l, int r)
	{
	memset(visited, 0, sizeof(visited));
	bool isTrue = false;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	{
	if (visited[i][j]) continue;
	queue<pair<int, int>> q;
	q.push({ i,j });
	visited[i][j] = true;
	//기록을 위한 스택
	stack<pair<int, int>> st;
	st.push({ i,j });
	int sum = a[i][j];
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; ++k)
	{
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < n)) continue;
	if (visited[ny][nx]) continue;
	int diff = abs(a[ny][nx] - a[y][x]);
	if (l <= diff && diff <= r)
	{
	q.push({ ny,nx });
	st.push({ ny,nx });
	visited[ny][nx] = true;
	// 연합이 생겼다면 true
	isTrue = true;
	sum += a[ny][nx];
	}
	}
	}
	int ret = sum / st.size();
	while (!st.empty())
	{
	int y = st.top().first;
	int x = st.top().second;
	st.pop();
	a[y][x] = ret;
	}
	}
	return isTrue;
	}
	int main()
	{
	cin >> n >> l >> r;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	cin >> a[i][j];
	int ans = 0;
	while (1)
	{
	if (bfs(l, r))
	ans++;
	else
	break;
	}
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub