백준 16234 인구 이동

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

 

서론

DFS/BFS 문제이며 DFS를 이용하여 구현

 

---

아이디어

국경선을 공유하는 연합을 만들기 위해 DFS를 사용한다.

모든 칸에서 DFS를 실행하고,

DFS에서 방문할 칸이 아직 방문하지 않은 칸이고 국경선 열림 조건에 부합하면 다음칸에 방문하면 된다.

그리고 방문할때마다 변수 pop에 칸의 인구를 더해주고, 변수 cnt를 +1 해주고 방문한 칸의 좌표를 벡터에 넣는다.

DFS가 끝나면 벡터를 이용하여 방문했던 좌표들의 인구를 pop/cnt로 갱신해준다.

 

이동(){
 for(a의 모든 좌표){
  pop=0
  cnt=0
  vector
  if (현재 좌표 방문 안했으면) dfs(좌표, pop, cnt, vector)
  for(idx : vector) a[idx] = pop/cnt
 }
}

dfs(좌표, pop, cnt, vector){
 다음 방문할 좌표 계산
 if(방문할 좌표가 국경선 조건에 부합하고 방문한적이 없다){
  pop+=a[좌표]
  cnt++
  visited[좌표]=1
  vector.push(좌표)
  dfs(다음좌표, pop, cnt, vector)
 }
 return
}

 

---

구현

//c++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

#pragma warning(disable : 4996)

int a[52][52];
int visited[52][52];
int n, l, r;

int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };

int uPopulation;
int uCnt;

void dfs(int y, int x, std::vector<std::pair<int, int>> &v) {

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= 0 && nx >= 0 && ny < n && nx < n && visited[ny][nx] == 0) {
			if (abs(a[y][x] - a[ny][nx]) >= l && abs(a[y][x] - a[ny][nx]) <= r) {
				uPopulation += a[ny][nx];
				uCnt++;
				visited[ny][nx] = 1;
				v.push_back({ ny, nx });
				dfs(ny, nx, v);
			}
		}
	}
	return;
}

bool move() {
	memset(visited, 0, sizeof(visited));

	// 인구 이동
	bool flag = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			std::vector<std::pair<int, int>>v;
			uPopulation = 0;
			uCnt = 0;
			if (visited[i][j] == 0) {
				dfs(i, j, v);
				if (v.size() > 0) { 
					flag = true; 
					for (int k = 0, size = v.size(); k < size; k++) {
						a[v[k].first][v[k].second] = uPopulation / uCnt;
					}
				}
			}
		}
	}

	return flag;
}


int main() {
	scanf("%d %d %d", &n, &l, &r);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	int result = 0;
	while (1) { 
		if (move() == false) break; 
		result++;
	}
	printf("%d", result);
}