백준 16234_인구 이동 문제풀이 in C++

in Devlog on Algorithm
  1. 문제 URL
  2. 문제 요구사항
  3. 접근 방법
  4. 풀이 순서
  5. 소스코드
  6. 문제 풀이 결과

문제 URL

https://www.acmicpc.net/problem/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번 보다 작거나 같은 입력만 주어진다.
  • 인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

접근 방법

  • flag 변수를 둬서 해당 flag값이 true 일 때만 (인구 이동이 있을 때만) 반복하도록 하고, 그 안에서 bfs 탐색을 수행한다.

풀이 순서

  1. N, L, R을 입력받고, N크기만큼의 Map 정보를 입력받는다
  2. flag (초기값 true) 값을 조건으로 둬서 while 반복문을 수행한다.
  3. while
    • flag에 false 값을 넣고, visited 배열을 false로 초기화한다.
    • visited의 각 인덱스를 조건으로 map 배열에 대해 bfs 탐색을 한다.
    • 탐색 전, v 벡터를 초기화 하고, 탐색 첫 인덱스 i 와 j를 벡터에 넣는다.
    • 또, sum에 해당 좌표의 값 map [ i ] [ j ] 값을 넣고 탐색을 수행한다.
    • 탐색 중 각 국가 사이의 차이가 L 이상 R 이하라면, sum에 map[nx][ny] 값을 넣고, visited는 true, v 벡터와 queue에 nx와 ny를 넣는다.
    • 해당 인덱스에 대해 bfs 탐색이 종료 되면, v 벡터의 사이즈를 검사하여 2보다 크면, 국경선을 열었다는 뜻이므로,
    • v 벡터의 각 인덱스 값들을 조회해서 map에 v벡터 각 인덱스 좌표 값에 sum / v.size() 값을 넣는다.
    • 다음 날로 넘어가기 위해 flag 값을 true로 조정한다.
    • while 반복문 종료 전, flag가 true라면 today(일 계산 변수) += 1을 한다.
    • 이와 같은 작업 반복
  4. today 출력

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

// N : 맵 크기, 국경선을 여는 L: 최소 범위, R: 최대 범위 --> L <= 인구 <= R
int N, L, R;
int map[50][50] = { 0, };
bool visited[50][50] = { false, };
vector<pair<int, int>> v;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int today = 0; 
bool flag = true;
int sum = 0;

void input() {
	cin >> N >> L >> R;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
}

void bfs(int x, int y) {
	visited[x][y] = true;
	queue<pair<int, int>> q;

	q.push({ x, y });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				if (!visited[nx][ny]) {
					int abs_value = abs(map[nx][ny] - map[xx][yy]);

					if (abs_value >= L && abs_value <= R) {
						sum += map[nx][ny];
						visited[nx][ny] = true;
						v.push_back({ nx, ny });
						q.push({ nx, ny });
					}
				}
			}
		}
	}
}

void solution() {

	while (flag) {
		flag = false;

		memset(visited, false, sizeof(visited));

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) {
					v.clear();
					v.push_back({ i, j });
					sum = map[i][j];
					bfs(i, j);
				}

				if (v.size() >= 2) {
					flag = true;

					for (int k = 0; k < v.size(); k++) {
						map[v[k].first][v[k].second] = sum / v.size();
					}
				}
			}
		}
		if (flag)
			today++;
	}
}

void output() {
	cout << today;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution();
	output();

	return 0;
}

문제 풀이 결과