백준 - 인구 이동 (16234) [C++]

이 문제는 bfs를 이용한 문제이다.

 

입력이 작기 때문에 구현만 하면 정답이 나오는 문제라고 생각했다.

 

국경선을 여는 것을 bfs를 이용해서 같은 연합에 속한 pair들을 담은 vector를 리턴하도록 만들었다.

이 때, 연합의 배열의 size가 N * N 이라는 것은 2개 이상 연결된 연합이 전혀 없다는 뜻이므로, 종료 조건이 된다.

 

이 배열을 사용하여 값을 계산하고, world 배열에 반영해주면 문제가 풀린다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

#define MAX 50

int N, L, R;
int world[MAX][MAX];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

bool inRange(int y, int x) {
	if (0 <= y && y < N && 0 <= x && x < N) {
		return true;
	}

	return false;
}

int absolute(int a) {
	if (a < 0) {
		return -a;
	}

	return a;
}

bool isPossible(int ny, int nx, int presentY, int presentX) {
	int dist = absolute(world[ny][nx] - world[presentY][presentX]);

	if (L <= dist && dist <= R) {
		return true;
	}

	return false;
}

vector<pair<int, int>> bfs(int startY, int startX, vector<vector<bool>> &visited) {
	visited[startY][startX] = true;
	queue<pair<int, int>> q;
	vector<pair<int, int>> result;

	result.push_back({ startY, startX });
	q.push({ startY, startX });

	while (!q.empty()) {
		pair<int, int> present = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = present.first + dy[i];
			int nx = present.second + dx[i];

			if (inRange(ny, nx) && !visited[ny][nx] &&
				isPossible(ny, nx, present.first, present.second)) {
				result.push_back({ ny, nx });
				visited[ny][nx] = true;
				q.push({ ny, nx });
			}
		}
	}

	return result;
}

vector<vector<pair<int, int>>> openDoor() {
	vector<vector<bool>> visited(N, vector<bool>(N, false));
	vector<vector<pair<int, int>>> result;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (!visited[y][x]) {
				vector<pair<int, int>> area = bfs(y, x, visited);
				result.push_back(area);
			}
		}
	}

	return result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> L >> R;
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> world[y][x];
		}
	}

	for (int day = 0; day <= 2000; day++) {
		vector<vector<pair<int, int>>> open = openDoor();

		if (open.size() == N * N) {
			cout << day << '\n';
			return 0;
		}

		for (vector<pair<int, int>> &area : open) {
			int acc = 0;

			for (pair<int, int> &element : area) {
				int y = element.first;
				int x = element.second;

				acc += world[y][x];
			}

			acc /= area.size();

			for (pair<int, int> &element : area) {
				int y = element.first;
				int x = element.second;

				world[y][x] = acc;
			}
		}
	}

	return 0;
}