[ 백준 17471 ] 게리맨더링 (C++)

[문제보기]

 

[해결과정]

 

 1. input : n, arr (int형) 배열에 각각의 인원수 담기

  -> 2차원 vector에 각각의 점에 간선 긋기

 

 2. dfs(int count, int r(레드갯수), int b(블루갯수))

  -> count != n+1 이라면, color에 색칠 후에 dfs(count+1, 색칠한곳+1, 색칠안한곳) 전송

  -> count == n+1 이라면 아래 3번 수행

 

 3. function

  -> red, blue 각각의 진영 갯수 0으로 초기화

  -> redSum, blueSum 각각의 총합 0으로 초기화

  -> 방문 체크 배열(check) 초기화

  -> rf, bf 플래그 초기화

 

  -> 1~N까지 점을 돌며, 레드 진영 한번, 블루 진영 한번.. 각각 한번씩 정점을 큐에 넣고 그 색에 대한 bfs()수행

   -> 진입할 때 색에 따라 rf, bf = true 설정

   -> bfs(색깔) 진입하면 아래 4번 수행

 

 4. bfs(int c)

  -> 해당 정점이 빨간색이면 red++, redSum += arr[node] 진영에 인원수 추가. 블루 동일.

  -> 큐에 있는 정점을 중심으로 붙어있는 점이 같은 색깔이라면 진입

 

 5. bfs(c) 수행이 완료되면 다시 dfs부분으로 돌아와서, bfs를 돌며 추가했던 red, blue가 현재 dfs의 r,b와 동일한지 확인.

  -> 동일하지 않다면 return;

  -> 동일하다면 ans = min(ans, abs(redSum - blueSum)); 수행

 

 6. output : 만약 ans가 987987987 이라면 -1 출력, 아니라면 ans 출력

 

[소스코드]

/*
    BOJ 17471 - 게리맨더링
    Created by haejun on 2020/02/27
    소요시간 : 35분
*/
#include<iostream>
#include<vector>
#include<memory.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
 
int n;
int arr[11];
int color[11];
int red, blue;
int redSum, blueSum;
int ans = 987987987;
 
//연결선 정보
vector <int> v[11];
 
queue<int> q;
bool check[11];
 
void bfs(int c) {
    while (!q.empty()) {
        int num = q.front();
        q.pop();
 
        if (c == 1) {
            red++;
            redSum += arr[num];
        }
        else {
            blue++;
            blueSum += arr[num];
        }
 
        for (int i = 0; i < v[num].size(); i++) {
            if (check[v[num][i]] == 0 && color[v[num][i]] == c) {
                check[v[num][i]] = 1;
                q.push(v[num][i]);
                
            }
        }
    }
}
 
void dfs(int cnt, int r, int b) {
    if (cnt == n+1) {
        //실행 할 곳
        red = 0; blue = 0;
        redSum = 0; blueSum = 0;
        memset(check, 0, sizeof(check));
        bool rf = false, bf = false;
 
        // 레드진영, 블루진영 각자 끼리끼리 다 연결되었는지 확인, 및 인원체크
        for (int i = 1; i <= n; i++) {
            if (rf == 1 && bf == 1) break;
            if (color[i] == 1 && check[i]==0 && rf==0) {
                rf = 1;
                check[i] = 1;
                q.push(i);
                bfs(1);
            }
            else if(color[i]==2 && check[i]==0 && bf==0){
                bf = 1;
                check[i] = 1;
                q.push(i);
                bfs(2);
            }
        }
        
 
        //레드진영, 블루진영 연결되었는지 확인
        if (red != r || blue != b) return;
 
        ans = min(ans, abs(redSum - blueSum));
 
        return;
    }
 
    color[cnt] = 1;
    dfs(cnt + 1, r+1, b);
 
    color[cnt] = 2;
    dfs(cnt + 1, r, b+1);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    // 1. input
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    int a, b;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        for (int j = 0; j < a; j++) {
            cin >> b;
            v[i].push_back(b);
        }
    }
 
    dfs(1, 0, 0);
    if (ans == 987987987) cout << -1 << "\n";
    else cout << ans << "\n";
 
 
 
    return 0;
}
 

 

[해결 과정 중 실수한 부분 / 잡담]

 A형 시험 볼 때, 풀었던 문제다.. 아마 내 생에 두번째 A형일 때다.. 이 때 아마,,, 거의 다 해결 했던 거 같은데 STL 문법을 잘 몰라서 못풀었던 기억이 난다. vector를 전역변수로 2차원으로 선언했는데.. 그 전역변수 vector를 초기화 하는 법을 몰랐다.. 단 v.clear()만 알았는데.. 2차원이라서 v[i].clear()형식으로 초기화 했어야 했다.. 멍청이.

 

 이번에 스터디 문제로 나와서 풀었는데 35분 걸렸다......................................... 실력이 는건가,, 아니면 기억속에 문제가 남아서 그랬을까.?

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트 기출, 삼성 상시테스트 A형 기출