백준 17471번 게리맨더링 C++ 백트래킹, DFS, BFS

리뷰

 

https://www.acmicpc.net/problem/17471

예제가 다 맞길래 제출했는데 1%에서 틀리길래 당황했다. 하지만 질문게시판에 존재하는 몇가지 반례를 보고 문제점을 파악하였다.

 

문제 풀이

1. n값을 받아주고 정답을 출력할 변수 ans를 10억으로 초기화 해준다.
2. 각 노드에 대해 투표권을  입력 받아주고, 인접 배열을 생성해 준다. 나는 노드를 0부터 시작했기 때문에 b에서 1을 빼줬다.
3. 벡터 a, b를 초기화 하고 dfs에 매개변수를 level = 0, 빈 벡터a, 빈 벡터b를 전달해 주고 실행하였다.
4. dfs에서는 level이 벡터에 들어있는 노드의 개수이자, 노드 자체를 나타낸다.
5. 벡터 a에 level 노드를 넣어주고 재귀를 실행한다, 재귀를 빠져나오면 a에서 노드를 빼준다.
6. 벡터 b에 level 노드를 넣어주고 재귀를 실핸한다, 재귀를 빠져나오면 b에서 노드를 빼준다.
7. 위 작업으로 level이 n에 도달했을때 벡터 a, b에 빈 벡터가 없다면 한단계 더 진행해 준다.
8. a와 b를 bfs를 돌려 각 벡터 안에 존재하는 노드들이 연결되어 있는지 확인해 준다.
9. a와 b에 저장된 노드들이 각각 서로 연결되어 있다면 한단계 더 진행해 준다.
10. a, b벡터 내 노드들의 투표권의 합계를 구한 뒤 그 차이만큼을 ans 변수의 최소값으로 초기화 해준다.
11. 재귀 작업을 모두 마친 후 ans값이 그대로 10억이라면 -1을 출력, 아니라면 ans에 저장된 값을 출력해 준다.

 

참고 사항

구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. = 양방향 그래프 생성

입력으로 주어지는 연결 노드는 모두 노드가 1부터 시작이라는 가정 하에 입력된다.

나는 노드 인덱스를 0부터 해서 b값을 빼주지 않아 틀렸었는데 어떻게 예제는 다 정답이 출력됐었는지 의문이다.

 

정답 코드

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
int n, ans;
int lst[10][10] = { 0, };
int men[10];

bool bfs(vector<int>& a) {
	int length = a.size();
	queue<int> q;
	q.push(a[0]);
	int v[10] = { 0, };
	v[a[0]] = 1;
	int cnt = 1;

	while (!q.empty()) {
		int cn = q.front(); q.pop();
		for (int i = 0; i < length; i++) {
			if (!v[a[i]] && lst[cn][a[i]]) {
				v[a[i]] = 1;
				cnt++;
				q.push(a[i]);
			}
		}
	}
	return cnt == length;
}

void dfs(int level, vector<int>& a, vector<int>& b) {
	if (level == n) {
		if (!a.empty() && !b.empty()) {
			if (bfs(a) && bfs(b)) {
				int A = 0, B = 0;
				for (int i = 0; i < a.size(); i++) A += men[a[i]];
				for (int i = 0; i < b.size(); i++) B += men[b[i]];
				ans = min(ans, abs(A - B));
			}
		}
		return;
	}

	a.push_back(level);
	dfs(level + 1, a, b);
	a.pop_back();

	b.push_back(level);
	dfs(level + 1, a, b);
	b.pop_back();
}

int main() {
	cin >> n;
	ans = 1e9;
	for (int i = 0; i < n; i++) cin >> men[i];
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		while (a--) {
			int b; cin >> b;
			b--;
			lst[i][b] = 1;
			lst[b][i] = 1;
		}
	}
	vector<int> a, b;
	dfs(0, a, b);
	if (ans == 1e9) cout << -1;
	else cout << ans;
}