17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
1.풀이 방법.
- 분류는 dfs로 하였다. (dfs를 통해서 연결된 같은 선거구를 탐색하였고)
- 선거구 1의 첫번째 구역을 기준으로 dfs를 한번 돌리고 , 선거구2의 첫번째 구역을 기준으로 dfs를 한번 수행했다.
- 그랬을때 방문을 체크하는 배열 check의 각 구역은 모두 true로 되어있어야 각 선거구가 모두 연결되어 있다는
뜻이다. (전 그렇게 체크하였습니다.)
- 처음에 조합을 만들어서(단 수의 제한이 없음 N개의 지역을 모두 선거구 1이 가져가는 것만 거르면 됨)
CASE를 만들어서 계산에 들어갔고 들어가서 선거구 2에 선거구1에 포함되지 않은 구역들을 넣어주어서
- 일단 CASE에 대한 선거구1,선거구2를 나누어 주었고 DFS를 돌려 연결되어있는지 확인후.
- 나누어진 선거구가 각자 모두 연결되어있다는 것이 확인되면 인구수의 합의 차이를 결과벡터에
삽입 해주고 소팅 후 최소값을 출력하였습니다.
2. 주의사항
- 전략을 처음에 세우고 들어갔는데..... 노트와 펜으로 세운 전략은 이랬습니다.
-<노트에 쓴 내용>
1. CASE를 만들자(분류)
2. DFS로 각 CASE가 유효한 CASE인지 확인하자(모두 각자 연결되어 있는지)
3. 인구수 차이를 측정
- 이렇게 세우고 코드를 작성하러 들어갔는데
- 순차적으로 짜다보니 코드가 매우 길어졌습니다.
- 그리고 전역변수에 대한 각 작업 수행시 초기화가 필요한 경우 추가로 함수를 작성하고 하다보니..
더 길어졌는데.....전략 뿐만아니라 조금 더 명확한 틀을 설정하려고 노력해야겠습니다.....
(코드가 길어지면 짜다 보면 막 헷갈리는 부분이 생기고 갑자기 멍해지기도 하고....;;)
3.나의코드
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
bool check[11]; //방문한 노드인지 확인
int groupindex[11]; //CASE별 각 구역이 어떤 선거구에 포함되어있는지 확인
vector<int> edges[11]; //연결된 간선 정보 저장
int peoplecount[11]; //각 구역별 인구수 저장변수
int tmp;
int N;
vector<int> votecamp1; //선거구1에 해당하는 구역을 담을 벡터
vector<int> resultmin;//각 CASE별 인구 수 차이를 담아놓을 변수
void input() {//입력받는 함수
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> peoplecount[i];
}
for (int i = 1; i <= N; i++) {
cin >> tmp;
for (int j = 0; j < tmp; j++) {
int n; cin >> n;
edges[i].push_back(n);
}
}
}
int getsum(vector<int> arr) { //인구수 합 구하는 함수
int s = 0;
for (int i = 0; i < arr.size(); i++) {
s += peoplecount[arr[i]];
}
return s;
}
void resetcheck() { //초기화함수
for (int i = 0; i < 11; i++) {
check[i] = false;
}
}
int gap(int num1, int num2) { //단순히 차이를 리턴하는 함수
if (num1 > num2) { return (num1 - num2); }
else { return (num2 - num1); }
}
void dfs(int index,int g) { //DFS수행
check[index] = true;
for (int i = 0; i < edges[index].size(); i++) {
if (check[edges[index][i]]==false&&groupindex[edges[index][i]] == g) {
//방문하지 않았고, 나와 같은 선거구 인 경우 탐색을 수행
dfs(edges[index][i],g);
}
}
return;
}
bool all() { //모두 방문했는지 체크를 위한 함수
for (int i = 1; i <= N;i++) {
if (check[i] == false) return false;
}
return true;
}
void groupindexreset() { //초기화 함수
for (int i = 0; i < 11; i++) {
groupindex[i] = 1;
}
}
void checkvotecamp() {
if (votecamp1.size() == N) { return; }
vector<int> votecamp2; //선거구2를 담을 변수
groupindexreset(); //각 지역이 어떤 선거구에 속했는지를 담을 변수 초기화
for (int i = 1; i <= N; i++) { //1에 속하지 않은 지역은 2에 넣기
bool c = false;
for (int j = 0; j < votecamp1.size(); j++) {
if (votecamp1[j] == i) { c = true; break; }
}
if (c == false) { votecamp2.push_back(i);
groupindex[i] = 2;
}
}
resetcheck();
dfs(votecamp1[0],1); //선거구의 지역이 모두 연결되어있는지 체크를 위해 DFS
dfs(votecamp2[0],2);
if (all() == true) {
int first = getsum(votecamp1);
int second = getsum(votecamp2);
resultmin.push_back(gap(first, second));
}
}
void makecase(int num) { //조합CASE(수가 정해지지 않은)
if (num > N) { return; }
for (int i = num; i <= N; i++) {
votecamp1.push_back(i);
checkvotecamp();
makecase(i + 1);
votecamp1.pop_back();
}
}
int main() {
// 1 ~ N 의 구역
input(); //입력
makecase(1); //케이스 만들자
sort(resultmin.begin(), resultmin.end()); //최소값 출력 부
if (resultmin.empty()) { cout << -1; return 0; }
cout << resultmin[0];
return 0;
}
'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 16234[C++] (0) | 2020.10.25 |
|---|---|
| 백준 18405 [C++] (0) | 2020.10.25 |
| 백준 18352 [C++] (0) | 2020.10.17 |
| 백준 2486 : 안전영역 (0) | 2020.03.22 |
| 백준 2583 (0) | 2020.03.02 |
