BOJ(C++) / 백준 16234 : 인구 이동

백준 16234 : 인구 이동

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

16234번: 인구 이동

 

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

 

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

 

코드

//백준 16234 인구 이동
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N, L, R;
vector<vector<int>> board;
int visited[51][51] = { 0, };
int nexti[4] = { 1,0,-1,0 }, nextj[4] = { 0,1,0,-1 };
int area_sum = 0, area_count = 0;
vector<pair<int, int>> together;

void DFS(int c_i, int c_j) {
	visited[c_i][c_j] = 1;
	area_sum += board[c_i][c_j]; //연합의 인구
	area_count++; //연합의 크기
	together.push_back({c_i, c_j});

	for (int k = 0; k < 4; k++) {
		int n_i = c_i + nexti[k];
		int n_j = c_j + nextj[k];
		if (n_i < 0 || n_j < 0 || n_i >= N || n_j >= N) {
			continue;
		}
		if (visited[n_i][n_j] == 0) {
			int x = max(board[c_i][c_j], board[n_i][n_j]) - min(board[c_i][c_j], board[n_i][n_j]);
			if (L <= x && x <= R) {
				DFS(n_i, n_j);
			}
		}
	}
}

int main() {
	//입출력 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//입력
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++) {
		vector<int> temp;
		for (int j = 0; j < N; j++) {
			int num;
			cin >> num;
			temp.push_back(num);
		}
		board.push_back(temp);
	}

	int answer = 0;
	while (1) {
		memset(visited, 0, sizeof(visited)); // 0으로 초기화
		int check = 0;
		vector<vector<pair<int, int>>> vec;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == 0) {
					together.clear(); // 초기화
					area_sum = 0; area_count = 0;
					DFS(i, j);
					//국경선이 열릴 수 있을 때
					if (together.size() != 1) {
						//가장 뒤에 sum, count추가
						together.push_back({ area_sum, area_count });
						vec.push_back(together);
						check = 1;
					}
				}
			}
		}

		//열릴 수 있는 국경선이 없을 때
		if (check == 0)
			break;
		else {
			//국경선을 열어 인구 이동
			for (int i = 0; i < vec.size(); i++) {
				int s_c = vec[i][vec[i].size() - 1].first / vec[i][vec[i].size() - 1].second;
				for (int j = 0; j < vec[i].size() - 1; j++) {
					board[vec[i][j].first][vec[i][j].second] = s_c;
				}
			}
		}
		answer++; //하루
	}
	
	cout << answer << "\n";


	return 0;
}

 

설명

벡터 vec에 연합을 이루는 i,j를 쌍으로 저장한다. 뒤에 (연합의 인구수), (연합을 이루고 있는 칸의 개수)를 push 하여 같이 저장한다. 

열릴 수 있는 국경선이 없을 때까지 반복하여 수행한다.

열릴 수 있는 국경선이 있을 때는 국경선을 열어 인구수를 업데이트 한다.

고찰

걸린 시간 : 한 시간

구글링 없이 문제를 풀었지만 시간이 조금 오래 걸렸다. 생각해야 할 것들이 많아서 오래 걸리긴 했지만 문제를 풀 수 있었다. 다른 사람의 풀이도 알아봐야겠다. 

 

난이도

Gold 5