백준 16234 인구이동 // ny,nx만처리하는 bfs / main에서 v[y][x]처리 / vector &v로 함수내 전역변수 사용

16234번: 인구 이동 (acmicpc.net)

16234번: 인구 이동

* dfs 조건처리는 contine만으로 가능, 빡구현필요X

if (abs(a[y][x] - a[ny][nx]) < l
			|| abs(a[y][x] - a[ny][nx]) > r)
			continue;

* for(v) 조건문실행되면 연결할게 있었다는 뜻 -> ret++, else break

조건문안에 flag=1  =>  연결할게잇는지없는지 검사

!flag 이면, 종료.

for (pair<int, int> p : v)
					{
						a[p.first][p.second] = sum / v.size();
						flag = 1;
					}

if (!flag) break;

 

while(true)

1. 탈출조건 : flag검사

2. dfs돌기전 초기화, y,x처리: sum=a[i][j], push(i,j) 

3. dfs (범위밖->컨틴뉴) :

3.1 초기노드를 v에넣고, visit처리

3.2 vSize==0이면 연결된게없음 -> 컨틴뉴

#include <bits/stdc++.h> 
using namespace std;
const int INF = 987654321;
int a[54][54];
int n,l,r,sum, dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 }, ret, y, x;
int visited[54][54];
vector<pair<int, int>> v;

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < n;
}
/*
* ny,nx만 처리하는 dfs
* y,x는 main에서 처리.
*/
void dfs(int y, int x, vector<pair<int, int>>& v)
{
	//visit[y][x] = 1;

	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (!in(ny, nx)) continue;
		if (visited[ny][nx])continue;
		if (abs(a[y][x] - a[ny][nx]) < l
			|| abs(a[y][x] - a[ny][nx]) > r)
			continue;
		visited[ny][nx] = 1;
		v.push_back({ ny,nx });
		sum += a[ny][nx];
		dfs(ny, nx,v);
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	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 = 0;
		fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j])
				{
					//x,y 를 영역으로 가정하고 push
					v.clear();
					visited[i][j] = 1;
					v.push_back({ i, j });
					sum = a[i][j];
					dfs(i, j, v);
					//연결된영역이없으면 패스
					if (v.size() == 1) continue;
					//연결된영역잇으면 종료조건아님.
					//flag=1
					for (pair<int, int> p : v)
					{
						a[p.first][p.second] = sum / v.size();
						flag = 1;
					}
				}

			}
		}
		if (!flag) break;
		ret++;

	}
	cout << ret;
}


	
/*
2 20 50
50 30
20 40
1 */