알고리즘 :: 백준 :: BFS :: 16234 :: 인구 이동

문제

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

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

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

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

문제접근

본 문제는 DFS로 풀이하는 것이 월등하게 빠릅니다.
현재는 BFS 풀이를 기준으로 포스트 하고, DFS 풀이 완료 후 글 수정하겠습니다.

BFS 풀이

• 임의의 땅으로부터 상, 하, 좌, 우로 인접한 국가들 중 인구 수의 차이가 $L \leq 인구차이 \leq R$ 인 경우라면 연합을 맺어야 한다.
• 인구 이동 발생 횟수의 의미를 잘 파악해야 한다.
  • 인구 이동 발생 횟수 = 시간 으로 생각하면 이해하기 쉽다.
  • 현재 N x N 땅에서 인구 이동이 1회 이뤄졌다는 의미는, 임의의 점 (i, j)에서 더 이상 인구 이동이 일어나지 않을 때 까지 인구 이동이 이뤄졌음을 의미한다.
  • 따라서 다시 (i, j)가 (0, 0)에서 시작해야 새롭게 인구 이동이 시작된다.
  • 본 코드에서는 i번째 인구 이동에서 실질적으로 인구 이동은 tempLand라는 2차원 배열에서 이뤄지고, 인구 이동이 종료된 뒤에 land에 복사/붙혀넣기 해주는 과정으로 이를 구현했다.
    • 왜냐하면, land에서 수정이 이뤄질 경우, 임의의 점 (i, j)에서 인구 이동이 발생한 결과가 적용이 되고, 이는 다음 임의의 점 (i, j)에 영향을 주기 때문이다.
• 임의의 땅으로부터 인구 이동이 발생할 수 있는 연합을 만드는 과정은 BFS로 구현할 수 있다.
• queue에서 pop()해서 얻은 땅의 좌표로부터 연합을 만들 수 있다면 연합에 포함된 땅의 개수를 카운트 하고, 인구 수를 증가시킨다.
• BFS가 종료되면 같은 그룹에 속해있는 모든 국가는 인구 이동의 결과 만큼 인구를 나눠갖는다.

코드

BFS 코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int N, L, R, land[50][50], tempLand[50][50], isVisited[50][50], answer;
constexpr int moving[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline bool isSafe(int y, int x) {
    return ((0 <= y && y < N) && (0 <= x && x < N));
}

inline void copyArr(int lhs[][50], int rhs[][50]) {
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            lhs[y][x] = rhs[y][x];
}

bool bfs(int startY, int startX, int groupNumber) {
    queue<pair<int, int>> q;
    q.push({startY, startX});
    isVisited[startY][startX] = groupNumber;  // 방문 표시
    int count = 1, sum = land[startY][startX];

    while(!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int ny = y + moving[i][0], nx = x + moving[i][1];
            if (isSafe(ny, nx) && isVisited[ny][nx] == 0) {
                int diff = abs(land[y][x] - land[ny][nx]);
                if (L <= diff && diff <= R) {
                    q.push({ny, nx});
                    isVisited[ny][nx] = groupNumber;
                    count++;
                    sum += land[ny][nx];
                }
            }
        }        
    }
    if (count > 1) {	// 연합이 발생했다면 인구 이동 시작.
        int newVar = sum / count;
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < N; ++x)
                if (isVisited[y][x] == groupNumber) tempLand[y][x] = newVar;
        return true;
    } else {
        isVisited[startY][startX] = 0;	// [중요] 연합이 발생하지 않았다면 방문표시 제거해줘야 한다.
        return false;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> L >> R;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            cin >> land[y][x];

    copyArr(tempLand, land);	// 실질적으로 결과가 반영되는 tempLand를 초기화한다.
	
    while (true) {
        bool loopFlag = false;	// 인구이동이 발생했다면 카운트 해주기 위한 플래그 변수.
        int groupNumber = 1;	// 각 그룹을 넘버링 하기 위한 변수.
        memset(isVisited, 0, sizeof(isVisited));

        for (int y = 0; y < N; ++y)
            for (int x = 0; x < N; ++x) {
                if (isVisited[y][x]) continue;
                if (bfs(y, x, groupNumber)) {
                    loopFlag = true;	// BFS 결과, 인구 이동이 발생했음.
                    groupNumber++;		// 다음 인구 이동을 위해 그룹 넘버 증가.
                }
            }
			// 모든 칸을 검사한 결과 인구 이동이 1회 이상 발생했으므로 카운팅하고 결과 반영.
        if (loopFlag) { answer++; copyArr(land, tempLand); }
        else break;
    }
    cout << answer << '\n';
}

1. BFS 결과는 tempLand에서 이뤄지며, 모든 칸을 검사해서 더 이상 인구 이동이 발생하지 않으면 인구 이동 카운트를 하나 올려주고, land에 결과를 반영한다.
2. BFS 함수에서 연합이 만들어지지 않는 경우, 첫 번째 칸을 방문 해제해주지 않으면 오류가 발생하므로 꼭 방문을 해제한다.

BFS 개선 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

static int N, L, R, land[50][50];
static bool flag, isVisited[50][50];
static queue<pair<int, int>> inputQueue;
static constexpr int moving[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

inline bool isSafe(int y, int x) {
    return ((0 <= y && y < N) && (0 <= x && x < N));
}
bool bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({y, x});
	isVisited[y][x] = true;
	vector<pair<int, int>> uni = {{y, x}};
	int sum = land[y][x];
	
	while (!q.empty()) {
		int y = q.front().first, x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + moving[i][0], nx = x + moving[i][1];
			if (isSafe(ny, nx) && !isVisited[ny][nx]) {
                int diff = abs(land[y][x] - land[ny][nx]);
                if (L <= diff && diff <= R) {
                    q.push({ny, nx});
                    isVisited[ny][nx] = true;
					uni.push_back({ny, nx});
                    sum += land[ny][nx];
                }
            }
		}
	}
	if (uni.size() > 1) {
		for (int i = 0; i < uni.size(); ++i) {
			land[uni[i].first][uni[i].second] = sum / uni.size();
			inputQueue.push(uni[i]);
		}
		return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> L >> R;
	for (int y = 0; y < N; ++y)
		for (int x = 0; x < N; ++x) {
			cin >> land[y][x];
			inputQueue.push({y, x});
		}
	int answer = 0;
	while (true) {
		flag = false;
		memset(isVisited, false, sizeof(isVisited));
		int qSize = inputQueue.size();
		while (qSize--) {
			int y = inputQueue.front().first, x = inputQueue.front().second;
			inputQueue.pop();
			if (isVisited[y][x]) continue;
			if (bfs(y, x)) flag = true;
		}
		if (!flag) break;
		answer++;
	}
	cout << answer << '\n';
}

결과

BFS 결과

BFS 개선코드 결과

DFS 결과