[백준OJ] 16234번 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

---

 

-풀이-

문제가 일단 잘못나온것 같다. 인구이동의 횟수를 구하였더니 오답이 나왔고, 인구이동을 며칠동안 했는지에 대해 구해줬더니 통과했다.

 

통과한 풀이 기준으로 설명을 하자면,

먼저 N*N배열을 탐색하며 자신기준 상,하,좌,우 나라와의 차이를 비교하여 L이상 R이하인 나라가 있다면, 이나라는 연합이 되므로, bfs를 실행해준다.

해당 연합은 각 연합의 총 인구수와 땅의 개수를 저장해두는 cal({총 인구수,땅}에 대한 벡터 )의 사이즈로 표시해준다.

 

{처음 연합이 되는 땅의 인구수,1} 을 cal에 push_back해준 뒤, 연합을 cal.size()로 표기해준다.

만약 bfs를 돌며 이 연합과 같은 연합이 된다면, push_back해준 값에다가 해당 땅의 인원을 더해주고, 땅의수를 +1해주며 bfs를 실행해준다.

 

이렇게 모든 연합들을 표기해주었다면, 다시 N*N배열을 탐색하며, 해당 연합에 대응하는 cal.first/cal.second의 값을 넣어주면된다.

 

만약 bfs를 다 돌고나서, cal의 사이즈가 0이 된다면, 더이상 이동할 인구가 없다는 뜻이므로, 종료해주고, 답을 출력해주면된다.

 

-코드-

 

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

int n, l, r, result = 0;
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int maze[50][50];

bool isIn(int x, int y) {
	return x >= 0 && x < n&&y >= 0 && y < n;
}

bool bfs() {
	int visited[50][50] = { 0 };
	vector<pair<int, int>> cal;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			queue<pair<int, int>> q;
			bool flag = false;
            //해당 좌표가 연합이 될 수 있는지 검사
			for (int k = 0; k < 4; k++) {
				int x = i + mv[k][0];
				int y = j + mv[k][1];
				int gap = abs(maze[i][j] - maze[x][y]);
				if (isIn(x, y) && gap >= l && gap <= r &&!visited[x][y]) {
					flag = true;
				}
			}
			if (!flag) continue;//연합이 아니라면, 다음거 검사
			else {
            	//연합이 되므로, push_back해준뒤, size로 연합 표기
				cal.push_back({ maze[i][j],1 });
				int calsize = cal.size();
				visited[i][j] = calsize;
				q.push({ i,j });
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;

					q.pop();
					for (int k = 0; k < 4; k++) {
						int nx = x + mv[k][0];
						int ny = y + mv[k][1];
						int gap = abs(maze[x][y] - maze[nx][ny]);
						if (isIn(nx, ny) && gap >= l && gap <= r && !visited[nx][ny]) {
							q.push({ nx,ny });
							visited[nx][ny] = calsize;
							cal[calsize - 1].first += maze[nx][ny];//해당 연합의 총인원 갱신
							cal[calsize - 1].second++;//해당 연합의 땅 개수 갱신
						}
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visited[i][j] != 0) {
				int ind = visited[i][j] - 1;
				maze[i][j] = cal[ind].first / cal[ind].second;
			}
		}
	}
	if (cal.size() == 0) {
		return false;
	}
	else {
		return true;
	}
}

void input() {
	cin >> n>>l>>r;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
		}
	}
}

void solve() {
	while (bfs()) {
		result++;
	}
	cout << result;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	input();
	solve();
}