✅ 재귀 (or DFS) ✅ BFS

문제

1. 문제 접근 및 해결 로직

로직을 크게 보면

1. 팀 나누기 (레드, 블루)
2. 가능한 방법인지 판단
3. 인구 차이의 최솟값 확인

2 ≤ N ≤ 10 범위가 작으므로 완전탐색으로 구현해도 문제가 없을 것 같다.

- 1) 팀 나누기

재귀를 활용할 것인데 그 이유는 각 지역이 빨간 팀이냐 아니냐에 따라 나눠지기 때문이다. (재귀 or DFS)

- 2) 가능한 방법인지 판단

연결요소의 수를 구하는 것과 같다. (BFS)

• 각선거구의 지역이 1개 이상이어야 한다.
• 각선거구의 지역들은 연결되어 있어야 한다.

- 3) 인구 차이의 최솟값 확인

가능한 방법으로 판단이 되었다면
선형 탐색으로 선거구의 지역별 인구의 합을 각각 구하여 차이를 구하고
최솟값을 최신화 한다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int people[11];       // 지역별 인구수
bool connect[11][11]; // 지역간 연결관계
bool area[11];        // 지역 지정 현황 (빨간색으로 지정하면 나머지는 파란색)
bool visited[11];     // 방문 체크
queue<int> que;
int N, ans = 999999;

bool BFS(vector<int> vec, bool color)
{
    fill(visited, visited + 11, false);
    que.push(vec[0]);
    visited[vec[0]] = true;
    int cnt = 1;

    while (!que.empty())
    {
        int num = que.front();
        que.pop();
        for (int i = 1; i <= N; i++)
        {
            if (visited[i] == false && connect[num][i] == true && area[i] == color)
            {
                cnt++;
                visited[i] = true;
                que.push(i);
            }
        }
    }

    if(vec.size() == cnt) return true;
    else return false;
}

bool is_possible()
{
    // 선거구에 따라 나눔
    vector<int> red, blue;
    for (int i = 1; i <= N; i++)
    {
        if (area[i] == true)
            red.push_back(i);
        else
            blue.push_back(i);
    }

    // 1. 선거구가 1개 이상이어야 함
    if (red.size() == 0 || blue.size() == 0)
        return false;

    // 2. 선거구의 지역들은 서로 연결 되어야 함
    if(BFS(red,true) == false || BFS(blue,false) == false) return false;

    return true;
}

void Set_area(int num, int cnt)
{ // num : 구역, cnt : 지정한 구역의 수
    if (cnt >= 1)
    { // 한개 이상 지정(빨강)부터는 팀이 나눠진 것이므로 최솟값 계산
        if (is_possible())
        {
            // 두 선거구의 인구 차이의 최솟값
            int cnt_r=0, cnt_b=0;
            for(int i=1;i<=N;i++){
                if(area[i] == true) cnt_r+=people[i];
                else cnt_b+=people[i];
            }
            ans = min(ans, abs(cnt_r-cnt_b));
        }
    }

    for (int i = num; i <= N; i++)
    {
        if (area[i] == false)
        {
            area[i] = true;
            Set_area(i, cnt + 1);
            area[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> people[i];
    }
    for (int i = 1; i <= N; i++)
    {
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++)
        {
            int num;
            cin >> num;
            connect[i][num] = true;
            connect[num][i] = true;
        }
    }

    Set_area(1, 0); // 1번부터 구역 지정

    if(ans==999999) cout << -1 << "\n";
    else cout << ans << "\n";

    return 0;
}

3. 시간 복잡도

BFS : N
DFS : 2^N
O(2^N)

4. Review

DFS를 활용한 구역 나누기 + BFS를 활용한 연결요소
둘 다 사용하는 특이한 문제