Problem 문제풀이
몇 가지 기본 개념을 묻는 문제였다. 기본기에 충실할 수록 빨리 풀 수 있는 문제이다.
-
그룹을 나누는 능력
-
그룹끼리 연결되어 있는지 탐색하는 능력
전략
-
input을 받으면서 구역간의 연결정보를 인접리스트에 저장한다.
-
A구역과 B구역으로 나누어주자.
-
각 구역이 조건에 맞는지 확인해주자.
-
조건에 맞다면 인구의 차를 구하여 answer를 갱신해주자.
먼저 인접리스트에 연결정보를 다 넣어준다.
vector<int> graph[11];
for (int i = 1; i <= N; i++)
{
cin >> num;
for (int j = 0; j < num; j++)
{
cin >> to;
graph[i].push_back(to);
}
}
이제 구역을 선거구 두 개에 분배하자. 편하게 A선거구, B선거구로 명명하겠다.
재귀함수를 이용해서 구현해보자.
void solve(int idx)
{
if (idx == N+1) //구역을 다 분배한 경우
{
//계산 중...
return;
}
A.push_back(idx);
solve(idx + 1);
B.push_back(A.back());
A.pop_back();
solve(idx + 1);
B.pop_back();
}
모든 구역을 A와 B에 잘 나누었으면 idx가 N+1이 되었을 것이다. 이제 나누어진 구역이 조건에 맞는지
확인을 해야한다. A나 B가 비어있으면 안 되고 같은 선거구의 구역끼리는 연결되어 있어야한다.
if (idx == N+1)
{
int sumA = 0;
int sumB = 0;
if (A.empty() || B.empty())
{
return;
}
for (int i = 1; i <= N; i++)
{
visited[i] = -1;
}
if (dfs(A, A[0]))
{
for (int i = 0; i < A.size(); i++)
{
sumA += arr[A[i]];
}
}
else
{
return;
}
for (int i = 1; i <= N; i++)
{
visited[i] = -1;
}
if (dfs(B, B[0]))
{
for (int i = 0; i < B.size(); i++)
{
sumB += arr[B[i]];
}
}
else
{
return;
}
int sub = sumA - sumB;
if (sub < 0)
{
sub *= -1;
}
if (answer == -1 || answer > sub)
{
answer = sub;
}
return;
}
dfs를 통해서 선거구 내에 연결이 안 된 구역이 없는지 확인을 해보자.
bool dfs(vector<int>& T, int idx)
{
visited[idx] = 1;
bool ret = true;
for (int i = 0; i < T.size(); i++)
{
if (visited[T[i]] == -1)
{
ret = false;
break;
}
}
if (ret)
{
return ret;
}
for (int i = 0; i < graph[idx].size(); i++)
{
int next = graph[idx][i];
for (int j = 0; j < T.size(); j++)
{
if (T[j] == next)
{
if (visited[next] == -1)
{
ret |= dfs(T, next);
}
break;
}
}
}
return ret;
}
실수만 하지 다면 그렇게 어려운 문제는 아닌 것 같다.
전체 코드를 남기며 마무리한다.
#include <iostream>
#include <vector>
using namespace std;
int N, num, to, answer;
int arr[11];
int visited[11];
vector<int> graph[11];
vector<int>A;
vector<int>B;
bool dfs(vector<int>& T, int idx);
void solve(int idx);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= N; i++)
{
cin >> num;
for (int j = 0; j < num; j++)
{
cin >> to;
graph[i].push_back(to);
}
}
answer = -1;
solve(1);
cout << answer;
return 0;
}
void solve(int idx)
{
if (idx == N+1)
{
int sumA = 0;
int sumB = 0;
if (A.empty() || B.empty())
{
return;
}
for (int i = 1; i <= N; i++)
{
visited[i] = -1;
}
if (dfs(A, A[0]))
{
for (int i = 0; i < A.size(); i++)
{
sumA += arr[A[i]];
}
}
else
{
return;
}
for (int i = 1; i <= N; i++)
{
visited[i] = -1;
}
if (dfs(B, B[0]))
{
for (int i = 0; i < B.size(); i++)
{
sumB += arr[B[i]];
}
}
else
{
return;
}
int sub = sumA - sumB;
if (sub < 0)
{
sub *= -1;
}
if (answer == -1 || answer > sub)
{
answer = sub;
}
return;
}
A.push_back(idx);
solve(idx + 1);
B.push_back(A.back());
A.pop_back();
solve(idx + 1);
B.pop_back();
}
bool dfs(vector<int>& T, int idx)
{
visited[idx] = 1;
bool ret = true;
for (int i = 0; i < T.size(); i++)
{
if (visited[T[i]] == -1)
{
ret = false;
break;
}
}
if (ret)
{
return ret;
}
for (int i = 0; i < graph[idx].size(); i++)
{
int next = graph[idx][i];
for (int j = 0; j < T.size(); j++)
{
if (T[j] == next)
{
if (visited[next] == -1)
{
ret |= dfs(T, next);
}
break;
}
}
}
return ret;
}