191016 백준 알고리즘 문제풀기

|

[16234] 인구 이동

  • 난이도: 중
    • 문제 이해 및 풀이 떠올리는데 30분, 구현 + 디버깅 해서 1시간 좀 안되게 소요
      • 총 80분정도 걸림
    • 처음엔 어렵겠다 생각했지만, 테스트 케이스를 이해한대로 하나한 풀어보며 문제를 완벽하게 이해할 수 있었다.
      • 반드시 문제를 100프로 이해하고 풀기 시작해야 한다!
    • BFS를 이용해서 비교적 쉽게 풀 수 있었다.
  • 문제
    • https://www.acmicpc.net/problem/16234
    • 처음에 N, L, R, NxN 크기의 맵이 주어진다.
      • N은 지도 가로세로 크기, L은 최소인원차, R은 최대인원차
    • 어떠한 국가는 1x1 칸 하나에 존재하며, 상하좌우 인접 국가와 인원차이가 L이상, R이하일 때 국경을 연다
      • 국경을 여는것은 같은 union으로 일단 묶은다음, 한번에 국경을 열어 인원들을 이동시킨다.
    • 같은 연합끼리 서로 국경이 열리면 모든 인원은 평균값으로 초기화된다. (소수 버림)
    • 만약 더 이상 인구 이동이 일어날 수 없으면 종료한다.
    • 총 인구이동이 몇 번 일어났는지를 출력한다.
  • 풀이
    • 문제를 쪼개보면
      • 입력을 받고
      • 입력 받은 맵에서 인구이동이 가능한 union끼리 묶고
        • 만약 이전 인구 이동 union과 현재 union이 같다면 종료
        • 더 이상 인구이동이 불가하므로
      • 인구를 이동시키고 국경을 닫는다.
      • 더 이상 인구이동이 불가할때까지 무한반복.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

int map[51][51]; // 인구맵
int c_union[51][51]; // 현재 연합
int p_union[51][51]; // 이전 연합

int dx[] = { -1,1,0,0 }; // 이동 방향
int dy[] = { 0,0,-1,1 };

// worst case 기준으로 배열 선언
int union_members[51 * 51]; // 해당 연합의 인원수
int union_cnts[51 * 51]; // 해당 연합의 국가수

bool open_wall(int cx, int cy, int nx, int ny, int L, int R)
{ // 조건을 만족하면 국경을 연다.
	int diff = abs(map[cy][cx] - map[ny][nx]);
	if (L <= diff && diff <= R) return true;
	else return false;
}

int main()
{
	int N, L, R;
	scanf("%d %d %d", &N, &L, &R);
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
		}
	}

	int move = 0;

	while (1)
	{
		//연합을 나누고
		int union_cnt = 1;
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				//모든 국가 중 union이 구분되었다면 넘어간다.
				if (c_union[j][i] != 0) continue;
				queue <pair<int, int>> q;
				c_union[j][i] = union_cnt;
				q.push(make_pair(i, j));
				while (!q.empty())
				{
					int cx = q.front().first;
					int cy = q.front().second;
					q.pop();
					for (int k = 0; k < 4; k++)
					{
						int nx = cx + dx[k];
						int ny = cy + dy[k];
						// 다음 국가 선택 범위 벗어나면 넘어간다.
						if (nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
						// 다음 국가가 분류 되어있다면 넘어간다.
						if (c_union[ny][nx] != 0) continue;
						//만약 벽을 열 수 있다면
            if (open_wall(cx, cy, nx, ny, L, R))
						{
							c_union[ny][nx] = union_cnt; // 같은 연합으로.
							q.push(make_pair(nx, ny));
						}
					}

				}
				union_cnt++; // 현재 연결된 모든 연합을 찾아 연결했으므로 다음으로 넘어간다.
			}
		}

		//연합을 비교해서 이전 연합과 같으면 종료
		int temp = 0;
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				if (c_union[j][i] == p_union[j][i]) temp++;
			}
		}
		if (temp == N * N) break;

		//나눠진 연합 내에서 인구수 구한담에
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				union_members[c_union[j][i]] += map[j][i]; // 해당 국가의 연합에 인원수 더하고
				union_cnts[c_union[j][i]]++; // 해당 union 인원수 계산
			}
		}

		//평균 인원수 구하고
		for (int i = 0; i < N*N; i++)
		{
      //만약 인원 없는 연합이라면 넘어간다.
			if (union_members[i] == 0) continue;
			union_members[i] = int(union_members[i] / union_cnts[i]);
		}

		//map에서 인구이동
		for (int j = 0; j < N; j++)
		{
			for (int i = 0; i < N; i++)
			{
				map[j][i] = union_members[c_union[j][i]]; // 인구 이동
				p_union[j][i] = c_union[j][i]; // 비교를 위해 이전 연합 저장
				c_union[j][i] = 0; // c_union 초기화
			}
		}
    move++; // 인구 이동 횟수 센다.
		
    //변수 초기화
		memset(union_members, 0, sizeof(union_members));
		memset(union_cnts, 0, sizeof(union_cnts));
	}

	printf("%d\n", move - 1); // while문의 중간에 현재 연합을 구하고 비교해 빠져나오므로 1을 뺀 값이 정답이 된다.

	//std::system("pause");
	return 0;
}