[백준]게리맨더링

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

17471번: 게리맨더링

현타... 하.. 나레기.. dfs의 동작순서 및 원리에 대해서 정확히 생각했어야됐는데 애초에 생각자체를 잘못(false그룹을 dfs를 통해 전부 연결되었는지 확인했고 true는 바로 dfs를 통해 묶어줬었는데 dfs로 묶으면 깊이탐색이기 때문에 안묶이는 경우가 생김... 또한 dfs로 개수세는 것도 파라미터로 len을 파고들어서 전체 개수를 센게 아니고 그냥 깊이만 셌었음)해서 첨엔 못풀었었다........ 하.. dfs재귀 구조에 대해서 다룰땐 유의해야 할 점이 많은거 같다...

오히려 재귀를 통해 머리가 아플때는 빠르게 bfs로 갈아타는게 좋은 것 같다... 훨씬 머리가 덜아프다. dfs의 경우 완전탐색(for문역할)으로 해주는경우가 간단하고 bfs로도 할수있으면 bfs가 더 낫다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
int N, ans = 1e9, cnt = 0, A_num, b_num;
int map[11][11];
int P[11],isV[11],isV2[11];
queue<int> q;
 
bool bfs(bool flag) {
    memset(isV2, false, sizeof(isV2));
    int start = 0, cnt = 1;
    for (int i = 1; i <= N; i++) { //flag를 통해 A,B그룹 둘다 컨트롤 가능.
        if (isV[i] == flag) { start = i; break; }
    }
    isV2[start] = true;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int i = 1; i <= N; i++) {
            if (isV[i] == flag && isV2[i] == false && map[v][i] == 1) { //같은 그룹 && bfs조건
                isV2[i] = true; q.push(i); cnt++; //여기서 세줘야 함 ~ push!
            }
        }
    } //탐색한 노드의 수가 전체 그룹노드의 수와 같은지.
    if (flag && cnt == A_num) return true;
    if (!flag && cnt == B_num) return true;
    return false;
}
 
void dfs(int s, int len) {
    if (len >= N ) return; //가지치기 모든 경우 탐색. N일때만 실행하는 것과 차이점.
    if (len >= 1) { //true가 없는 것 방지.
        A_num = 0;
        for (int i = 1; i <= N; i++) {
            if (isV[i])A_num++;
        }B_num = N - A_num;
        
        bool A = bfs(true); //파라미터를 통해 함수를 하나로만들어서 컨트롤.
        bool B = bfs(false);
        if (A&B) { //둘다 true이면 진행.
            int sum1 = 0,sum2 = 0;
            for (int i = 1; i <= N; i++) {
                if (isV[i])sum1 += P[i];
                else sum2 += P[i];
            }
            if (ans >= abs(sum1 - sum2)) ans = abs(sum1 - sum2);
        }
    }
 
    for (int i = s; i <= N; i++) {
        if (!isV[i]) { //조합.
            isV[i] = true; dfs(i, len + 1); isV[i] = false;
        }
    }
}
 
void solve() {
    dfs(1, 0); //조합을 통해 일단 그냥 2개로 찢는다
    printf("%d\n", ans == 1e9 ? -1 : ans);
}
 
int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> P[i];
    for (int i = 1; i <= N; i++) {
        int k;
        cin >> k;
        for (int m = 0; m < k; m++) {
            int z; cin >> z;
            map[i][z] = 1; map[z][i] = 1;
        }
    }
    solve();
    return 0;
}