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

23 Oct 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 16234 : 인구 이동(링크)

알고리즘

1. 브루트포스
2. 완전탐색
3. Connected Component
4. DFS

풀이

1. 계속 반복 -> 무한 반복 (while 문)
2. 어떠한 정점에서 부터 DFS 를 진행하여야 한다
   • dfs의 조건 l이상 r미만
3. 인구이동이 일어나지 않을 때 무한 반복문 종료

코드

// BOJ-16234 : 인구이동
#include<bits/stdc++.h>
using namespace std;

int n, l, r, sum = 0, cnt;

int a[54][54], visited[54][54];

const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

vector<pair<int, int>> v;

void dfs(int y, int x, vector<pair<int,int>> &v)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= n || nx >= n || visited[ny][nx]) continue;

		if (abs(a[ny][nx] - a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r)
		{
			visited[ny][nx] = 1;
			v.push_back({ ny, nx });
			sum += a[ny][nx];
			dfs(ny, nx, v);
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> l >> r;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}
	}
	while (true)
	{
		bool flag = 0; // 인구 이동이 일어났는지 체크하는 불린 값
		memset(visited, 0, sizeof(visited));

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (!visited[i][j])
				{
					v.clear();
					visited[i][j] = 1;
					v.push_back({ i,j }); // 변경할 좌표도 필요
					sum = a[i][j];
					dfs(i, j, v);
					if (v.size() == 1) continue;
					for (pair<int, int> b : v)
					{
						a[b.first][b.second] = sum / v.size();
						flag = 1;
					}
				}
			}
		}
		if (!flag) break;
		cnt++;
	}

	cout << cnt << '\n';

	return 0;
}

평가

• 모든 정점을 완전 탐색하는 알고리즘 + 각 지점에서 DFS를 통해 탐색해 나가는 알고리즘
  • 매 테스트케이스를 진행할 때 방문처리 배열은 다시 초기화 하여야 한다
  • 조건에 맞는 지점을 찾았을 때, pair<int,int> 형 vector를 미리 선언하여 그 좌표를 미리 담아두는 방법을 사용할 수도 있다.