백준 16234 인구 이동 [BruteForce]

문제 링크: https://www.acmicpc.net/problem/16234

16234번: 인구 이동

문제 풀이

문제가 쉬운 거 같았지만, 예제 마지막 테케를 보고 살짝 꼬여있다는 것을 알았습니다.

 

서로 연합이 되려면 나의 국가와 다른 국가의 차이가 L 이상 R이하가 되어야 서로 연합이 될 수 있습니다.

 

문제를 잘게 쪼개서 순서를 세우면 다음과 같습니다.

1. 입력을 받습니다.

2. 인구 이동이 가능한지 mark로 표시합니다. (백준 문제에서 단지 번호 붙이기 2667)처럼 단지로 mark 표시

3. 이 때 인구 이동을 했다면, 인구 이동을 시작하고 그 연합의 평균을 구해서 모두 평균값으로 맞추어줍니다.

2 ~ 3을 반복합니다. (만약에 인구 이동을 하지 않았다면, 무한루프를 탈출하면 됩니다.)

 

하나하나 자세하게 펼쳐서 설명해보겠습니다.

 

 

2. 인구 이동이 가능한지를 mark로 표시합니다.

예를 들어 다음과 같은 표가 있다고 합시다.

4 10 50 (N, L, R)

 

10 100 50 50

50 50 50 50

50 50 50 50

50 50 100 50

 

(0, 0)부터 dfs로 탐색하면서 상하좌우를 보면서 나의 국가와 다른 국가의 차이가 L 이상 R이하라면 mark로 표시해줍니다. 이때 visit [i][j] = mark로 표시했습니다. (2차원 visit배열을 따로 둠)

 

1 0 0 0

1 0 0 0

0 0 0 0

0 0 0 0

 

(0, 1)로 다시 dfs시작

1 2 2 0

1 2 0 0

0 0 0 0

0 0 0 0

 

(2, 2)로 다시 dfs시작

1 2 2 0

1 2 0 0

0 0 3 0

0 3 3 3

 

visit배열은 위의 상태로 끝나게 됩니다.

 

3. 이때 인구 이동을 했다면, 인구 이동을 시작하고 그 연합의 평균을 구해서 모두 평균값으로 맞추어줍니다.

우리는 mark를 3까지 했으므로 확실히 인구 이동을 했습니다. 만약에 인구 이동을 하지 않았다면

mark는 1이고 이는 탈출로 이어지면 됩니다.

 

mark 순서대로, 1번 단지들끼리 연합의 평균을 구해서 넣어줍니다.

 

mark가 1인 부분은 (0, 0)의 10과 (1, 0)의 50입니다.

total = 10 + 50 = 60

average = 60 / 2 = 30

 

mark가 2인 부분은 (0, 1)의 100, (0, 2)의 50, (1, 1)의 50입니다.

total = 100 + 50 + 50 = 200

average = 200 / 3 = 66

 

mark가 3인 부분은 (2, 2)의 50, (3, 1)의 50, (3, 2)의 100, (3, 3)의 50

total = 50 + 50 + 100 + 50 = 250

average = 250 / 4 = 62

 

30 66 66 50

30 66 50 50

50 50 62 50

50 62 62 62

이 됩니다. 이는 인구 이동을 1번 했다는 것을 의미합니다.

 

소스 코드

#include <iostream>
#include <cmath>
using namespace std;

int a[51][51];
int visit[51][51];
int N, L, R;

int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int mark;
bool mark_check;

void dfs(int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (visit[nx][ny] != 0) continue;
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
		{
			int diff = abs(a[x][y] - a[nx][ny]);
			if (diff >= L && diff <= R)
			{
				visit[x][y] = mark;
				visit[nx][ny] = mark;
				mark_check = true;
				dfs(nx, ny);
			}
		}
	}
}

void show()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << a[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void calculate(int door)
{
	int total = 0, cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == door)
			{
				cnt++; // 구역 카운트
				total += a[i][j]; // 총합 
			}
		}
	}

	int average = total / cnt; // 평균값을 구한다.
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == door)
			{
				a[i][j] = average; // 모든 연합을 같은 평균값으로 색칠
			}
		}
	}
}

void initialize()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			visit[i][j] = 0;
		}
	}
}
void movement_check()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == 0)
			{
				dfs(i, j);
				// 이동이 가능한 인구를 표시했다면, mark를 증가시켜 다음을 준비한다.
				if (mark_check) mark++; 
				mark_check = false;
			}
		}
	}
}

void movement()
{
	// mark가 1부터 색칠해진 곳부터 탐색해서 계산한다.
	int start = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visit[i][j] == start)
			{
				calculate(start);
				start++;
			}
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> N >> L >> R;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> a[i][j];
		}
	}

	int ans = 0;
	while (1)
	{
		initialize();
		mark = 1;

		movement_check(); 	  // 인구 이동이 가능한지 표시(Mark)한다.
		if (mark == 1) break; // 인구 이동을 하지 않았으면 종료
		                  
		ans++; 
		movement();           // 인구 이동 시작!!
	}
	cout << ans;
	return 0;
}