[BOJ 16234] 인구 이동

문제출처

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

16234번: 인구 이동

 

문제풀이

BFS로 전체탐색하면 되는 문제이다. 

BFS탐색을 통해 연합국가들을 찾으며 총 인구수와 연합국가 수를 구한다. 연합국가가 있는 경우 값을 문제조건대로 갱신해주고 연합국가가 없는경우 인구이동이 일어난 회수를 출력해주면 된다.

이때 연합국가의 좌표를 vector에 저장해 따로 관리해 주면서 갱신해줬다. 삼성기출문제가 점점 응용력이 필요해지는 것 같다. 문제를 주의깊게 읽고 완벽히 이해한뒤 소스코드를 작성하도록 해야겠다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_16234/BOJ_16234/boj16234.cpp

sw93/algorithm

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
bool flag;
int n, l, r, ans;
int dy[] = { 0, -1, 0, 1 };
int dx[] = { 1, 0, -1, 0 };
int map[50][50];
bool visit[50][50];
vector<pair<int, int> > v;
void init() {
	cin >> n >> l >> r;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
void bfs(int y, int x) {
	int count = 1, sum = map[y][x];
	queue<pair<int, int> > q;
	q.push(make_pair(y, x));
	v.push_back(make_pair(y, x));
	visit[y][x] = 1;
	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		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 || visit[ny][nx]) continue;

			int diff = abs(map[y][x] - map[ny][nx]);
			if (diff >= l && diff <= r) {
				visit[ny][nx] = 1;
				sum += map[ny][nx];
				count++;
				q.push(make_pair(ny, nx));
				v.push_back(make_pair(ny, nx));
			}
		}
	}

	if (v.size() > 1) {
		flag = 1;
		int updateValue = sum / count;
		for (int i = 0; i < v.size(); i++) map[v[i].first][v[i].second] = updateValue;	
	}
	v.clear();
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	while (true) {
		memset(visit, 0, sizeof(visit));
		flag = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (visit[y][x]) continue;
				bfs(y, x);
			}
		}
		if (flag) ans++;
		else break;
	}
	cout << ans << "\n";
	return 0;
}