[백준]16234 인구이동(C++)

백준 16234 인구이동

1. 문제

문제링크

2. 접근법

• 문제 접근
  • 국경선을 상 하 좌 우로 열수 있고 각 나라와 L, R을 기준으로 연합하기 때문에 DFS로 완전탐색하면서 각 나라와 연합한다.
  • 각 나라와 연합여부를 체크할 배열, 연합 후의 인구수 유지를 위해 연합한 나라의 좌표(행, 열)을 담을 벡터, n*n크기의 땅에 해당하는 배열이 필요하다.
  • 연합을 위해 while문을 돌리고 while문 내에 flag를 생성한다. 각 나라에 방문하지 않은 경우, 위에 선언한 배열과 벡터값을 초기화 시키고 DFS를 돌린다. 
  • 연합하기 위해서는 나라의 수가 2이상이어야 하므로 2이상이면 연합한 국가와 인구수를 더하고 연합한 나라의 개수로 나눠 평균을 구한다. 또한 이때 flag를 true로 바꾼다.
  • 연합 후 인구수 유지를 위해 선언한 벡터에 연합한 나라의 위치를 넣어준 뒤 벡터의 사이즈만큼 for문을 돌리면서 n*n배열에 위에서 구한 평균값을 넣어준다.
  • flag가 true인 경우 answer를 증가시킨다.

3. 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cstring>
#include<fstream>
using namespace std;
int N, L, R, cnt = 0, sum = 0;
int map[51][51];	//n*n크기의 땅
vector<pair<int, int>> vec;	//연합 후 인구수 유지를 위해 연합한 나라의 위치를 담을 벡터(행, 열)
bool checked[51][51]; //각 나라의 연합여부 체크할 배열 
//상 하 좌 우
int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };

void DFS(int row, int col)
{
	//4방향으로 탐색하면서 DFS를 돌림
	for (int i = 0; i < 4; i++)
	{
		int sr = row + dr[i];
		int sc = col + dc[i];

		//해당 위치에 방문하지 않았고 두나라의 인구차이가 L이상 R미만이면
		//sum 에 두나라의 인구수를 더해준 뒤 연합한 나라+1 시킨다.
		//후에 연합한 나라의 인구수를 업데이트 시켜주기 위해 
        	//vec에 해당나라의 위치(행, 열)를 넣는다.
		if (!checked[sr][sc])
		{
			if (0 <= sr && sr < N && 0 <= sc && sc < N)
			{
				int val = abs(map[row][col] - map[sr][sc]);
				if (L <= val && val <= R)
				{
					checked[sr][sc] = true;
					sum += map[sr][sc];
					cnt++;
					vec.push_back(make_pair(sr, sc));
					DFS(sr, sc);
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int ans = 0, avg = 0;
	cin >> N >> L >> R;

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

	while (1)
	{
		//flag, 체크배열 초기화
		bool flag = false;
		memset(checked, false, sizeof(checked));
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				//방문하지 않았다면
				if (!checked[i][j])
				{
					//vec, cnt, sum, 체크배열 초기화
					vec.clear();
					cnt = 1;
					sum = map[i][j];
					checked[i][j] = true;
					//인구이동을 위해 처음 입력받은 나라의 위치를 넣고 DFS를 돌림
					vec.push_back(make_pair(i, j));
					DFS(i, j);
					//연합한 나라가 2이상이면 avg값을 구하고 
					//연합한 나라의 인구수를 avg로 업데이트시킴
					if (cnt >= 2)
					{
						flag = true;
						avg = sum / cnt;
						for (int k = 0; k < vec.size(); k++)
						{
							map[vec[k].first][vec[k].second] 
                            							= avg;
						}
					}
				}
			}
		}
		if (!flag)
			break;
		else
			ans++;
	}
	cout << ans << "\n";
	return 0;
}

4. 시간복잡도

DFS 알고리즘에서 인접행렬 이용한 방법이므로 기본적으로 O(V^2)의 시간복잡도를 가진다.

5. 결과