BOJ_16234 : 인구 이동

👉 문제링크

16234번: 인구 이동

---

---

🔸 문제 분석 🔸

• 땅 크기(N)와 인구 최소, 최대값(L,R)이 주어지고, 2차원 배열 형태의 인구수가 주어진다.
• 인구수의 차이가 L, R 값 사이라면, 국경선을 연다.
  • 국경선이 열려서 통행이 가능한 나라들을 한 그룹으로 묶는다.
  • 한 그룹의 평균 인구수를 그룹내 모든 칸에 채운다. (인구를 평준화한다)
  • 이 평준화 작업은 BFS로 구현하면 될 것 같다.
• 국경선이 한 곳이라도 열렸다면, 인구 이동이 있으므로 하루가 지나야 한다.

 

🔸 코드 🔸

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

using namespace std;

int BFS(vector<vector<int>>& A, int& i, int& j, vector<vector<int>>& group,
			int& G_count, int& L, int& R, vector<vector<int>>& same_G_list) {
	int sum = 0;
	queue<vector<int>> q;
	vector<int> pair(2);
	pair[0] = i;
	pair[1] = j;

	q.push(pair);
	group[i][j] = G_count;

	while (!q.empty()) {
		pair = q.front();
		int now_i = pair[0];
		int now_j = pair[1];
		sum += A[now_i][now_j];
		same_G_list[G_count].push_back(now_i);
		same_G_list[G_count].push_back(now_j);
		//printf("pair[0] : %d    pair[1] : %d     G_count : %d\n", pair[0], pair[1], G_count);

		// left
		int next_i = now_i;
		int next_j = now_j - 1;
		if (next_j >= 0 && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//top
		next_i = now_i - 1;
		next_j = now_j;
		if (next_i >= 0 && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//right
		next_i = now_i;
		next_j = now_j + 1;
		if (next_j < A.size() && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//bottom
		next_i = now_i + 1;
		next_j = now_j;
		if (next_i < A.size() && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		q.pop();
	}

	return sum;
}

int main(void) {
	int N, L, R, day = -1, G_count;
	cin >> N >> L >> R;
	vector<vector<int>> A(N, vector<int>(N, 0));

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

	bool flag = true;
	while (flag) {
		flag = false;
		vector<vector<int>> group(N, vector<int>(N, 0)); // 소속 그룹
		vector<int> groupSum(N * N + 1, 0);
		vector<vector<int>> same_G_list(N * N + 1, vector<int>());
		G_count = 0;

		// 모든 나라를 방문하며 BFS 준비
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (group[i][j] == 0) {	// 소속 그룹이 없다면 BFS 시작
					G_count++;
					groupSum[G_count] = BFS(A, i, j, group, 
							G_count, L, R, same_G_list);

					if (groupSum[G_count] > A[i][j])
						flag = true;
						// flag = true면 다음 날 검사를 다시 해야함
				}
			}
		}

		// 그룹 평균 처리
		for (int g = 1; g <= G_count; g++)
		{
			int size = same_G_list[g].size();
			int avg = groupSum[g] / (size / 2);

			for (int c = 0; c < size; c+=2)
			{
				A[same_G_list[g][c]][same_G_list[g][c + 1]] = avg;
			}
		}
		day++;
	}
	cout << day;

	return 0;
}

 

🔸 코드 해석 🔸

코드가 꽤 길고 복잡하므로 끊어서 설명한다.

 

먼저 main함수의 while문 겉 부분이다.

int main(void) {
	int N, L, R, day = -1, G_count;
	cin >> N >> L >> R;
	vector<vector<int>> A(N, vector<int>(N, 0));

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

	bool flag = true;
	while (flag) {
		// 생략
	}
	cout << day;

	return 0;
}

• N, L, R, A 는 문제의 정의와 같다. (A는 vector를 중첩해서 사용했다)
• day : 인구 이동이 일어나는 일자 수
• G_count : 그룹 번호를 매기기 위한 변수 (1~N*N)
• flag : while문 내에서 국경선이 열리면 true

다음은 while문 안쪽이다.

    while (flag) {
        flag = false;
        vector<vector<int>> group(N, vector<int>(N, 0)); // 소속 그룹
        vector<int> groupSum(N * N + 1, 0);
        vector<vector<int>> same_G_list(N * N + 1, vector<int>());
        G_count = 0;

        // 모든 나라를 방문하며 BFS 준비
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (group[i][j] == 0) {	// 소속 그룹이 없다면 BFS 시작
                    G_count++;
                    groupSum[G_count] = BFS(A, i, j, group, 
                            G_count, L, R, same_G_list);

                    if (groupSum[G_count] > A[i][j])
                        flag = true;
                        // flag = true면 다음 날 검사를 다시 해야함
                }
            }
        }

        // 그룹 평균 처리
        for (int g = 1; g <= G_count; g++)
        {
            int size = same_G_list[g].size();
            int avg = groupSum[g] / (size / 2);

            for (int c = 0; c < size; c+=2)
            {
                A[same_G_list[g][c]][same_G_list[g][c + 1]] = avg;
            }
        }
        day++;
    }

• flag는 바로 false로 바꿔주고 국경선이 열린게 확인되면 true로 바꾼다.
• group : BFS의 방문 확인용 리스트 겸, 소속된 그룹을 기록하는 vector 이다. ( 0이면 미방문 )
• groupSum : 각 그룹 별 평균을 구하기 위해 총 합을 기록하는 vector 이다. ( 최대 값은 G_count의 최대값인 N*N )
• same_G_list : 같은 그룹의 좌표를 기록한 vector이다.
  ( i, j를 순서대로 넣는다. 3중첩은 안되고 pair를 굳이 넣고싶진 않아서... )
• 첫 2중 for문은 나라들을 한 번씩 방문하며 그룹에 속하지 않은 곳을 BFS의 시작점으로 삼는 반복문이다.
  • BFS의 반환값으로 한 그룹의 총 합을 받는데, 시작 나라와 같다면 그룹에 나라가 1개인 것 이므로 국경선이 열리지 않았다고 판단한다.
  • 원래는 void나 bool값을 반환하는 식으로 짰는데 마지막 평균값 처리에서 시간을 단축하기 위해 sum과 list를 추가하다 보니 이런식으로 바뀌었다.
• 두번째 2중 for문은 그룹들을 각 평균값으로 바꿔주는 부분이다.
  • 원래코드는 모든 나라를 1~G_count 까지 늘려가며 방문하고 평균값 처리를 하는데, 반복 횟수가 너무 많아져서 시간초과가 떴고, 위와 같이 총합과 list를 가록하도록 변경했다.
  • 나라의 좌표 2개를 순서대로 넣었으므로 2씩 늘려가며 평균값으로 바꿔준다.

 

다음은 BFS 함수이다.

int BFS(vector<vector<int>>& A, int& i, int& j, vector<vector<int>>& group,
			int& G_count, int& L, int& R, vector<vector<int>>& same_G_list) {
	int sum = 0;
	queue<vector<int>> q;
	vector<int> pair(2);
	pair[0] = i;
	pair[1] = j;

	q.push(pair);
	group[i][j] = G_count;

	while (!q.empty()) {
		pair = q.front();
		int now_i = pair[0];
		int now_j = pair[1];
		sum += A[now_i][now_j];
		same_G_list[G_count].push_back(now_i);
		same_G_list[G_count].push_back(now_j);
		//printf("pair[0] : %d    pair[1] : %d     G_count : %d\n", pair[0], pair[1], G_count);

		// left
		int next_i = now_i;
		int next_j = now_j - 1;
		if (next_j >= 0 && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//top
		next_i = now_i - 1;
		next_j = now_j;
		if (next_i >= 0 && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//right
		next_i = now_i;
		next_j = now_j + 1;
		if (next_j < A.size() && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		//bottom
		next_i = now_i + 1;
		next_j = now_j;
		if (next_i < A.size() && group[next_i][next_j] == 0 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) >= L 
					&& abs(A[now_i][now_j] - A[next_i][next_j]) <= R) {
			pair[0] = next_i;
			pair[1] = next_j;
			q.push(pair);
			group[next_i][next_j] = G_count;
		}

		q.pop();
	}

	return sum;
}

•  BFS 부분을 main() 안에 구현하면 너무 꼬일 것 같아 함수로 분리했다.
  (필요한 인자를 매개변수에 전부 넣게되서 좀 지저분해졌다...)
• 현재 좌표의 그룹 총합을 더해주고, 그룹 목록에도 추가한다.
• 현재 좌표를 기준으로 왼쪽, 위쪽, 오른쪽, 아래쪽을 탐색한다. 
  • vector 범위를 벗어나지 않는지 확인한다.
  •  group[][] == 0  : 방문하지 않았던 (그룹이 없는) 나라인지 확인한다.
  • L ~ R 범위 내인지 확인한다.
  • 좌표를 큐에 넣고, 그룹도 표시한다.

예제 4, 5 풀이 과정...!

---

🔸 end 🔸

• BFS를 적용해보니 생각보다 뼈대를 코딩하는 건 오래걸리지 않았다.
• 자잘한 오류가 많았고, 시간초과를 해결하는게 조금 힘들었다.
• 풀이 과정 사진처럼 손으로 풀어보니 문제 이해가 빠르게 되었다.