[C++] 백준(BOJ) - 17471 : 게리멘더링

13 Nov 2023 in Develop on C++, Algorithm

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

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

문제

백준(BOJ) - 17471 : 게리멘더링(링크)

알고리즘

1. 브루트포스
2. DFS
3. 비트마스킹

풀이

1. 양방향 간선을 인접 행렬로 받기
2. 색칠할 수 있는 모든 경우의 수를 확인하기
3. DFS를 통해 양쪽의 방향에서 DFS를 진행 (색칠된 것과 아닌 것)
4. 두개로 쪼개져 있다면 (두 connected component 사이즈의 합이 전체 구역 크기와 같다) 두 구역의 인구수의 합의 최소값을 만드는지 확인해나가며 res를 갱신

코드

// BOJ-17471 : 게리멘더링
#include<bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, m, res = INF;
int population[11], comp[11], visited[11];

vector<int> adj[11];

// <사이즈, 인구수>
pair<int, int> dfs(int here, int value)
{
	visited[here] = 1;
	pair<int, int> res = { 1, population[here] }; // {본인사이즈 = 1, 인구수}
	for (int there : adj[here])
	{
		if (comp[there] != value) continue;
		if (visited[there]) continue;
		pair<int, int> _tmp = dfs(there, value);
		res.first += _tmp.first;
		res.second += _tmp.second;
	}
	return res;
}

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

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> population[i];

	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		for (int j = 0; j < m; j++)
		{
			int tmp;
			cin >> tmp;
			adj[i].push_back(tmp);
			adj[tmp].push_back(i);
		}
	}

	// 비트마스킹을 통해 모든 경우의 수 체크, 0과 1<<n 은 One-side 이기 때문에 제외
	for (int i = 1; i < (1 << n) - 1; i++)
	{
		fill(comp, comp + 11, 0); // Red, Blue 구역 초기화
		fill(visited, visited + 11, 0); // 방문지역 초기화

		int idx1 = -1, idx2 = -1; // DFS 시작 지점 인덱스

		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
			{
				comp[j + 1] = 1;
				idx1 = j + 1;
			}
			else idx2 = j + 1;
		}
		pair<int, int> comp1 = dfs(idx1, 1);
		pair<int, int> comp2 = dfs(idx2, 0);

		if (comp1.first + comp2.first == n) // 두 connected component가 정확히 두개로 쪼개져 있다면 
			res = min(res, abs(comp1.second - comp2.second)); // 두 구역의 인구수 차를 최소값을 만드는 값을 구한다
	}

	cout << (res == INF ? -1 : res) << '\n';

	return 0;
}

평가

• 비트마스킹과 DFS 두가지 모두 연습할 수 있는 좋은문제
• Connected Component에 대한 개념을 복습하기
• void 형 dfs 이외에 int, pair<int,int> 형 등 다양한 리턴에 해당하는 dfs 함수 사용에 익숙해지기
• 최소, 최대 구하기 기본 매커니즘 이해