문제
백준 BOJ 17471 게리맨더링
입력
첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다. 셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다. 구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.
출력
첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.
제한
2 ≤ N ≤ 10
1 ≤ 구역의 인구 수 ≤ 100
풀이
N이 10밖에 되지 않으므로 그냥 완탐을 돌려도 괜찮을꺼라고 생각했다.
두개의 그룹으로 나누어 각 그룹들의 인구합의 차의 최솟값을 구해야한다.
첫번째 방법 (실패)
- 그룹1과 그룹2를 분할 (dfs사용)
- dfs를 사용할 경우에는 같은 레벨의 지역들이 grouping이 되어지지 않았다. -> 분할하면서 그룹핑을 확인하려 했기때문에 실패함.
- 모든 경우를 탐색할 수 없었기 때문에 최솟값을 구할 수 없었다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
int n,k,t;
vector<int>g[11];
int visited[11];
int visTmp[11];
int num[11];
int ans=-1;
void chkNode(int x){
// 현재노드 x인 위치에서 방문안한위치로 방문
for(int i=0;i<g[x].size();i++){
int nxt=g[x][i]; // 다음 위치
if(visTmp[nxt]==0){
visTmp[nxt]=2;
chkNode(nxt);
}
}
}
void go(int x, int cnt, int res) {
// 다 골랐으면 가능여부 확인하고 최솟값 계산하기
if(cnt==res){
// 각 경우마다 초기화해줘야해서 visTmp 필요함
for(int i=1;i<=n;i++)
visTmp[i]=visited[i];
// 현재까지 인구수 sum 계산
int sum=0;
for(int i=1;i<=n;i++){
if(visTmp[i]==1)
sum+=num[i];
}
// 방문안한지점 아무곳에서나 dfs돌려도 모두 이어져아함 ????
// dfs가 그냥 안되는것같음
// 방문안한곳 아무데나 찾기
int chk=0;
for(int i=1;i<=n;i++){
if(chk==1)break;
if(visTmp[i]==0){
chk=1;
// 방문안한지점인 해당노드와 나머지 방문안한 모든 지점이 연결되어야함
visTmp[i]=2;
chkNode(i);
// 하나라도 방문안한지점있으면 연결불가능
for(int j=1;j<=n;j++){
if(visTmp[j]==0){
return;
}
}
}
}
// 여기까지 왔으면 구역을 나눌 수 있다는 소리임.
int tmp=0;
for(int i=1;i<=n;i++){
tmp+=num[i];
}
if(tmp>2*sum){
tmp-=sum*2;
}
else tmp=sum*2-tmp;
if(ans==-1)ans=tmp;
else {
ans=min(ans,tmp);
}
return;
}
for(int i=0;i<g[x].size();i++){
// 방문안한곳이면
if(visited[g[x][i]]==0){
visited[g[x][i]]=1;
go(g[x][i],cnt+1,res);
visited[g[x][i]]=0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
}
int tmp;
for(int i=1;i<=n;i++){
cin>>k; // 인접구역수
for(int j=0;j<k;j++){
cin>>tmp; // 인접구역번호
g[i].push_back(tmp);
}
}
// 다 넣었음.
// 완탐돌려서 최솟값 확인하기
// -> 어떻게 확인할것인가?
// 선거구 나누기
for(int i=1;i<=n;i++){
// 나눠진 선거구역들
for(int j=1;j<=n;j++){
// i개까지 선거구역을 선택 -> 재귀로
visited[j]=1;
go(j,1,i); // j번째 선거구역을 i번까지 고름
visited[j]=0;
}
}
cout<<ans<<"\n";
return 0;
}
두번째 방법 (시간초과)
- 그룹1과 그룹2를 분할
- dfs를 사용하여 그룹을 나눈 후
- bfs를 사용하여 그룹이 연결되어있는지 확인함
- 모든 경우를 탐색하여 최솟값을 올바르게 구할 수 있었음
- 근데 시간초과남
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
int n,k,t;
vector<int>g[11];
int visited[11]={0,};
int visTmp[11]={0,};
int num[11]={0,};
int ans=-1;
bool isval(){
return true;
}
void go(int x, int cnt, int res) {
// 다 골랐으면 가능여부 확인하고 최솟값 계산하기
// bfs를 통해서 나눠진 그룹 정당성 확인
if(cnt==res){
// 그룹1은 visited => 1
// 그룹2는 visited => 0으로 되어있음
// 각 그룹내 노드가 이어져있는지 확인
// 그룹1의 아무노드, 그룹2의 아무노드 집어서 bfs수행해보자.
// 그룹1과 그룹2가 모두 타당하면 계산 ㄱ
queue<int>qa;
bool flagA = true;
int vis1[11]={0,};
// 그룹1 노드넣기
for(int i=1;i<=n;i++){
if(visited[i]==1){ // 1인걸로 bfs
vis1[i]=1;
qa.push(i);
break;
}
}
//그룹1 연결확인
while(qa.size()){
int cur = qa.front();
qa.pop();
for(int i=0;i<g[cur].size();i++){
int nxt=g[cur][i];
if(visited[nxt]==1&&vis1[nxt]==0){
vis1[nxt]=1;
qa.push(nxt);
}
}
}
for(int i=1;i<=n;i++){
if(visited[i]==1){
if(vis1[i]==0){
flagA=false;
break;
}
}
}
queue<int>qb;
bool flagB = true;
int vis2[11]={0,};
// 그룹2 노드넣기
for(int i=1;i<=n;i++){
if(visited[i]==0){ // 0인걸로 bfs
qb.push(i);
vis2[i]=1;
break;
}
}
//그룹2 연결확인
while(qb.size()){
int cur = qb.front();
qb.pop();
for(int i=0;i<g[cur].size();i++){
int nxt=g[cur][i];
if(visited[nxt]==0&&vis2[nxt]==0){
vis2[nxt]=1;
qb.push(nxt);
}
}
}
for(int i=1;i<=n;i++){
if(visited[i]==0){
if(vis2[i]==0){
flagB=false;
break;
}
}
}
if(flagA && flagB){
int a,b;
a=b=0;
for(int i=1;i<=n;i++){
if(visited[i]==0) a+=num[i];
else b+=num[i];
}
int sum=abs(a-b);
if(ans==-1) {
ans=sum;
}
else{
ans=min(ans,sum);
}
}
return;
}
// dfs를 통해서 그룹만 분할함
for(int i=1;i<=n;i++){
// 방문안한곳이면
if(visited[i]==0){
visited[i]=1;
go(i,cnt+1,res);
visited[i]=0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
}
int tmp;
for(int i=1;i<=n;i++){
cin>>k; // 인접구역수
for(int j=0;j<k;j++){
cin>>tmp; // 인접구역번호
g[i].push_back(tmp);
}
}
// 다 넣었음.
// 완탐돌려서 최솟값 확인하기
// -> 어떻게 확인할것인가?
// 선거구 나누기
for(int i=1;i<=n;i++){
// 나눠진 선거구역들 => dfs로 나누고 bfs로 확인
for(int j=1;j<=n;j++){
// i개까지 선거구역을 선택 -> 재귀로
visited[j]=1;
go(j,1,i); // j번째 선거구역을 i번까지 고름
visited[j]=0;
}
}
cout<<ans<<"\n";
return 0;
}
세번째 방법 (ok)
- 다른분들 코드 참고해서 뒤엎고 새로 풀었다..
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
int num[11];
int visited[11];
bool chk[11];
int res=1e9;
vector<int> g[11];
void dfs(int x, int cnt){
for(int i=0;i<g[x].size();i++){
if(chk[g[x][i]]==false&&visited[g[x][i]]==cnt){
chk[g[x][i]]=true;
dfs(g[x][i],cnt);
}
}
}
bool chking(){
for(int i=1;i<=n;i++){
if(visited[i]==1){
chk[i]=true;
dfs(i,1);
break;
}
}
for(int i=1;i<=n;i++){
if(visited[i]==0){
chk[i]=true;
dfs(i,0);
break;
}
}
for(int i=1;i<=n;i++){
if(chk[i]==false) return false;
}
return true;
}
void go(int cnt){
if(cnt==n){
memset(chk,false,sizeof(chk));
if(chking()){
int sum1=0, sum2=0;
for(int i=1;i<=n;i++){
if(visited[i]==1){
sum1+=num[i];
}else{
sum2+=num[i];
}
}
int result = abs(sum1-sum2);
if(res>result) res=result;
}
return;
}
visited[cnt+1]=1;
go(cnt+1);
visited[cnt+1]=0;
go(cnt+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>num[i];
}
for(int i=1;i<=n;i++){
cin>>k;
for(int j=0;j<k;j++){
int tmp;
cin>>tmp;
g[i].push_back(tmp);
}
}
go(0);
if(res==1e9) res=-1;
cout<<res;
return 0;
}
완씨의 개발기록