[알고리즘] 백준 17471 게리멘더링 // 비트마스킹, dfs 구역체크는 노드1곳에서 시작

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

* 행동영역

• dfs 구역체크는 노드1곳에서만 시작해라

 

* 오답정리

• 이전에 dfs를 모든노드에서 하고있었음
• 그런데, 연결확인을 위해서는 첫노드에서 시작하는것만으로 충분함!
• 필요없이 

• 반례) 1-2 / 3-4 인경우
  • 1,2,3이 구역1에 묶일때, visit 체크를 맨위에서 해주기때문에 {1,2,3}은 한구역이라고 잘못판단함.
  • 애초에 구역 1에서 dfs를 했으면 이런 문제가 없음!

 

* 의사코드

전체 코드의 흐름을 단계별로 정리:

1. **입력 처리**
   - N개의 구역과 각 구역의 인구수 입력
   - 각 구역별로 인접한 구역 정보를 입력받아 양방향 그래프 생성

2. **모든 가능한 분할 시도** (비트마스킹 활용)
   - 1부터 2^N-1까지 모든 경우의 수를 검사
   - 각 비트가 1이면 구역1, 0이면 구역2로 할당
   - 매 시도마다 방문 배열과 구역 표시 배열을 초기화

3. **각 분할에서의 처리**
   - 각 비트에 따라 노드들을 구역1(a1)과 구역2(a2)로 나눔
   - 각 노드가 어느 구역에 속하는지 is_area1, is_area2 배열에 표시

4. **구역1의 연결성 검사**
   - 구역1의 첫 번째 노드에서 DFS 시작
   - DFS는 같은 구역의 노드만 방문
   - 구역1의 모든 노드가 방문되었는지 확인
   - 방문되지 않은 노드가 있다면 연결되지 않은 것으로 판단하고 실패

5. **구역2의 연결성 검사**
   - 구역2의 첫 번째 노드에서 DFS 시작
   - 마찬가지로 같은 구역의 노드만 방문
   - 구역2의 모든 노드가 방문되었는지 확인
   - 방문되지 않은 노드가 있다면 실패

6. **인구 차이 계산**
   - 두 구역 모두 연결되어 있다면
   - 각 구역의 인구 수 합계 계산
   - 두 구역의 인구 차이 계산
   - 현재까지의 최소 차이값과 비교하여 갱신

7. **결과 출력**
   - 가능한 분할이 하나도 없었다면 -1 출력
   - 있었다면 찾은 최소 인구 차이 출력

주요 포인트:
- 각 구역이 서로 연결되어 있는지 확인하기 위해 각 구역의 첫 노드에서만 DFS 시작
- 두 구역은 겹치지 않으므로 방문 배열을 초기화할 필요 없음
- 한 구역이라도 연결되어 있지 않으면 해당 분할은 무효

 

 

* 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,ret=987654321;
int ingu[14], vis[14], is_area1[14], is_area2[14];
set<int> adj[14]; // adj[i]: i와 연결된 목록, 중복제거

void dfs1(int here) {
    vis[here]=1; // 무조건 방문처리 해버리는게 문제임

    for(auto next : adj[here]) {
        if(vis[next]) continue;
        if(is_area2[next]) continue; // 다른구역인경우
        dfs1(next);
    }
}

//구역이다르면 리턴 ,(노드n, 구역k)
void dfs11(int n) {
    if (vis[n]) return;
    if (is_area2[n]) return;
    vis[n] = 1;
    for (auto nxt : adj[n]) {
        dfs11(nxt);
    }
    return;
}

//구역이다르면 리턴 ,(노드n, 구역k)
void dfs22(int n) {
    if (vis[n]) return;
    if (is_area1[n]) return;
    vis[n] = 1;
    for (auto nxt : adj[n]) {
        dfs22(nxt);
    }
    return;
}

void dfs2(int here) {
    vis[here]=1;

    for(auto next : adj[here]) {
        if(vis[next]) continue;
        if(is_area1[next]) continue; // 다른구역인경우
        dfs2(next);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;

    for(int i=1;i<=n;++i) {
        cin>>ingu[i];
    }

    for(int i=1;i<=n;++i) {
        int cnt; // 인접한 구역의 수
        cin>>cnt;
        for(int j=0;j<cnt;++j) {
            int tmp;
            cin>>tmp;
            adj[i].insert(tmp);
            adj[tmp].insert(i); // 양방향
        }
    }

    // for(int i=1;i<=n;++i) {
    //     for(auto n : adj[i]) {
    //         cout<<n<<" ";
    //     }
    //     cout<<"\n";
    // }

    for(int i=1;i<(1<<n);++i) {
    // for(int i=3;i<4;++i) {
        vector<int> a1,a2; //구역1, 구역2
        memset(vis,0,sizeof(vis));
        memset(is_area1,0,sizeof(is_area1));
        memset(is_area2,0,sizeof(is_area2));
        
        for(int j=0;j<n;j++) {
            if(i & (1<<j)) { // 비트 1은 1번구역
                // a1 |= j;
                a1.push_back(j+1);
                is_area1[j+1]=1;
            }
            else { //비트 0은 2번구역
                // a2 |= j;
                a2.push_back(j+1);
                is_area2[j+1]=1;
            }
        }

        int is_possible=1; // 초기화 주의! (0으로 초기화해놓고있었네?)
        int ingu1=0,ingu2=0;
        //dfs1
        if(!a1.empty()) {
            dfs1(a1[0]);
            for(auto k : a1) {
                if(!vis[k]) {
                    is_possible = false;
                    break;
                }
                ingu1 += ingu[k];
            }
        }

        // 구역2 연결성 체크
        if(!a2.empty()) {
            dfs2(a2[0]);
            for(auto k : a2) {
                if(!vis[k]) {
                    is_possible = false;
                    break;
                }
                ingu2 += ingu[k];
            }
        }

        for(int k=1;k<=n;++k) {
            if(!vis[k]) is_possible=false;
        }

        if(is_possible) {
            int gab=abs(ingu1-ingu2);
            ret=min(ret,gab);
        }
    }

    if(ret==987654321) {
        cout<<-1;
        return 0;
    }
    cout<<ret;
    
    return 0;
}

 

 

* 큰돌 코드

• dfs가 pair를 반환한다. 여기에 상태를 저장한다. < 방문한 노드수, 인구합 >

1. dfs(1):
   방문[1] = true
   ret = {1, a[1]}      // {1, 5} 초기화
   재귀호출 dfs(2)...
   
2. dfs(2):
   방문[2] = true
   ret = {1, a[2]}      // {1, 4} 초기화
   재귀호출 dfs(3)...
   
3. dfs(3):
   방문[3] = true
   ret = {1, a[3]}      // {1, 3} 초기화
   재귀호출 dfs(4)...
   
4. dfs(4):  // leaf node
   방문[4] = true
   ret = {1, a[4]}      // {1, 2} 반환
   
5. dfs(3)로 돌아옴:
   ret.first += 1       // {1+1, 3+2}
   ret.second += 2      // {2, 5} 반환
   
6. dfs(2)로 돌아옴:
   ret.first += 2       // {1+2, 4+5}
   ret.second += 5      // {3, 9} 반환
   
7. dfs(1)로 돌아옴:
   ret.first += 3       // {1+3, 5+9}
   ret.second += 9      // {4, 14} 최종 반환

• comp[i] = 1 // 노드 i는 1번구역이다.
• comp[i] = 0 // 노드 i는 0번구역이다.
• 해당노드가 몇번구역인지만 배열에 기록, 벡터에 저장할필요 X!

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;  
int n, a[11], m, temp, ret = INF, comp[11], visited[11];
vector<int> adj[11]; 
pair<int, int> dfs(int here, int value){
    visited[here] = 1; 
    pair<int, int> ret = {1, a[here]}; 
    for(int there : adj[here]){
        if(comp[there] != value) continue; 
        if(visited[there]) continue; 
        pair<int, int> _temp = dfs(there, value); 
        ret.first += _temp.first; 
        ret.second += _temp.second;  
    }
    return ret; 
}  
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n; 
    for(int i = 1; i <= n; i++){
        cin >> a[i];  
    }
    for(int i = 1; i <= n; i++){
        cin >> m; 
        for(int j = 0; j < m; j++){
            cin >> temp; 
            adj[i].push_back(temp); 
            adj[temp].push_back(i); 
        } 
    }
    for(int i = 1; i < (1 << n) - 1; i++){
        fill(comp, comp + 11, 0);
        fill(visited, visited + 11, 0);
        int idx1 = -1, idx2 = -1; 
        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) ret = min(ret, abs(comp1.second - comp2.second)); 
    } 
    cout << (ret == INF ? -1 : ret)<< "\n";
}