[BFS&구현] 백준 16234 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
using namespace std;
int n, L, R;
int A[101][101] = { 0, };
bool visit[101][101];	
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int cnt;
int sum;

struct m {
	int x, y;
};

void initVisit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0;j < n;j++) {
			visit[i][j] = false;
		}
	}
}
vector <m> B;
void bfs(int a, int b) {
	queue <m> q;
	q.push({ a,b });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		B.push_back({ x, y });
		sum += A[x][y];
		q.pop();
		for (int i = 0;i < 4;i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			if (0 <= nx && nx < n && 0 <= ny && ny < n && visit[nx][ny] == false && L <= abs(A[nx][ny]-A[x][y]) && abs(A[nx][ny] - A[x][y]) <= R) {
				visit[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}
}
void calculate() {
	int sol = sum / (int)B.size();
	for (int i = 0; i < B.size();i++) {
		A[B[i].x][B[i].y] = sol;
	}
}

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 (1) {
		int ans = 0;
		for (int i = 0; i < n;i++) {
			for (int j = 0;j < n;j++) {
				if (!visit[i][j]) {
					visit[i][j] = true;
					sum = 0;
					bfs(i, j);
					if (B.size() > 1) {
						++ans;
						calculate();	
					}
					B.clear();
				}
			}
		}
		if (ans == 0)
			break;
		++cnt;
		initVisit();
	}
	cout << cnt;
}

저번에 말했던 친구가 추천해준 삼성 SW 문제 중 하나였다. 일단 기본적인 BFS와 크게 다른게 없지만 제일 막혔던 부분은 => 하루가 지나면 연합에 의한 인구이동 때문에 A배열의 원소들이 바뀌어야 되는데 어떻게 처리할지가 관건이였다. 해결방법은 새로운 벡터를 하나 만들어서 거기에 copy를 해두는 것 이였다. 이번 문제로 벡터를 이해하는데 조금 도움이 되고 친구한테도 많은 도움을 받았다. 그래서 오늘 알게된 새로운 내용들을 언제한번 따로 정리해 보려고 한다.