백준 16234 - 인구 이동

문제 링크입니다 https://www.acmicpc.net/problem/16234

16234번: 인구 이동

삼성 SW 역량테스트 문제입니다. BFS를 이용해 풀었습니다.

 

N*N의 입력이 주어졌을 때, 위의 조건을 따라서 인구 이동이 시작합니다.

 

 

왼쪽 그림은 인구 이동 전, 오른쪽 그림은 인구 이동 후의 모습입니다. 모든 나라가 국경선을 공유하기에 전부 인구가 달라진 모습을 볼 수 있습니다.

 

 

접근 방법

 

1. 이중 for문을 통해서 check배열의 값이 0일때 해당 칸부터 BFS를 시작해 국경선을 공유할 수 있는 칸을 찾는다.

2. 칸을 찾은 뒤 해당 칸들을 백터에 저장하고 탐색이 끝난 뒤에 해당 칸들의 인구들을 바꿔준다.

3. 인구 이동을 한번도 안할 경우, 인구 이동을 한 시간을 출력한다.

4. 인구 이동을 한번 이상 했을 경우 시간을 하나 증가시킨다.

 

 

BFS로 탐색을 하면서 인구 이동을 할 수 있는 국가들을 백터에 저장해주는 것이 핵심입니다!!

두 나라 간의 차이가 음수일 수 있기에 절댓값을 저장하기 위해 int c = abs(a,b)를 사용했습니다.

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int N, L, R;
int people[51][51];
int check[51][51];
int arr[4] = { 1,0,-1,0 };
int arr2[4] = { 0,1,0,-1 };
int time_;
int cnt;

void find_(int a, int b, int c) {
	vector<pair<int, int>> V;
	queue<pair<pair<int,int>,int>> q;
	q.push(make_pair(make_pair(a,b),c));
	V.push_back(make_pair(a, b));
	check[a][b] = 1;
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int s = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + arr[i];
			int yy = y + arr2[i];
			int gap = abs(people[xx][yy] - s);
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= N) {
				if (check[xx][yy] == 0 && (gap >= L && gap <= R)) {
					check[xx][yy] = 1;
					q.push(make_pair(make_pair(xx,yy),people[xx][yy]));
					V.push_back(make_pair(xx, yy));
				}
			}
		}
	}
	if (V.size() > 1) {
		cnt++;
		int sum = 0;
		for (int i = 0; i < V.size(); i++) {
			sum += people[V[i].first][V[i].second];
		}
		sum /= V.size();
		for (int i = 0; i < V.size(); i++) {
			people[V[i].first][V[i].second] = sum;
		}
	}
}

void solve() {
	while (1) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (check[i][j] == 0) {
					find_(i, j, people[i][j]);
				}

			}
		}
		memset(check, 0, sizeof(check));
		/*for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				cout << people[i][j] << " ";
			}
			cout << "\n";
		}*/
		if (cnt == 0) {
			cout << time_;
			break;
		}
		else {
			cnt = 0;
			time_++;
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> L >> R;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> people[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!