알고리즘/백준
백준 17471 (게리맨더링) - java
김다미김태리신시아
2023. 8. 1. 21:56
https://www.acmicpc.net/problem/17471
17471번: 게리맨더링
선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.
www.acmicpc.net
문제 : 게리맨더링 (17471)
유형 : 조합론 + BFS
접근
- 선거구를 2개의 영억으로 나눈다. (조합론 사용)
- 각 선거구에 대하여 BFS를 수행한다. (2개의 영역에 대해서 총 BFS 2번 수행)
- 방문하지 못한 도시가 있다면 -1
- 모든 도시를 방문했다면 각 영역의 인구수의 차이를 구한다.
- 최솟값을 구한다 !
조합론
- 조합론에 대한 구현은 백트랙킹을 사용하였다.
코드
static void go(int start,int r,int b)
{
if(r>=n || b >=n)
return; // 한 영역이 모든 점을 포함할 수 없다 !
if(r+b == n) // 모든 영역의 배분이 완료되었다면
{
int tmp = search(); // 차이를 구한다.
if(tmp != -1)
result = Math.min(result,tmp); // 최솟값 갱신
return;
}
for(int i=start;i<=n;i++)
{
if(!visit[i])
{
visit[i] = true;
color[i] = 1; // 1의 영역
go(i+1,r+1,b);
color[i] = 2; // 2의 영역
go(i+1,r,b+1);
color[i] = 0;
visit[i] = false;
}
}
}탐색 : BFS 사용
- 1의 영역 , 2의 영역 2개에 대하여 2번의 BFS를 수행해야 한다.
코드
static int search()
{
Queue<Integer> qr = new LinkedList<>();
Queue<Integer> qb = new LinkedList<>();
boolean[] v = new boolean[n+1];
int rsum = 0;
int bsum = 0;
for(int i=1;i<=n;i++)
{
if(color[i] == 1)
{
qr.add(i); // 1의 영역 지점중 한개만 추출
v[i] = true;
rsum += num[i];
break;
}
}
for(int i=1;i<=n;i++)
{
if(color[i] == 2)
{
qb.add(i); // 2의 영역 지점중 한개만 추출
v[i] = true;
bsum += num[i];
break;
}
}
// 1의 영역에 대한 BFS
while(!qr.isEmpty())
{
Integer cur = qr.poll();
for(int next : graph[cur])
{
if(!v[next] && color[next] == 1)
{
v[next] = true;
rsum += num[next];
qr.add(next);
}
}
}
// 2의 영역에 대한 BFS
while(!qb.isEmpty())
{
Integer cur = qb.poll();
if(!v[cur])
{
v[cur] = true;
bsum += num[cur];
}
for(int next : graph[cur])
{
if(!v[next] && color[next] == 2)
{
v[next] = true;
bsum += num[next];
qb.add(next);
}
}
}
for(int i=1;i<=n;i++)
{
if(!v[i])
{
return -1; // 방문하지 못한 지점이 있다면 잘못된 분할인 것이다 !
}
}
return Math.abs(rsum - bsum); // 차이를 반환
}전체 코드
import java.util.*;
import java.io.*;
public class Main {
static int n = 0;
static int[] num;
static ArrayList<Integer>[] graph;
static boolean[] visit;
static int[] color;
static int result = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
num = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=1;i<=n;i++)
{
num[i] = Integer.parseInt(st.nextToken());
}
graph = new ArrayList[n+1];
visit = new boolean[n+1];
color = new int[n+1];
for(int i=1;i<=n;i++)
{
graph[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine()," ");
int num = Integer.parseInt(st.nextToken());
for(int j=1;j<=num;j++)
{
graph[i].add(Integer.parseInt(st.nextToken()));
}
}
go(1,0,0);
if(result == Integer.MAX_VALUE)
{
System.out.println(-1);
}
else{
System.out.println(result);
}
br.close();
}
static void go(int start,int r,int b)
{
if(r>=n || b >=n)
return;
if(r+b == n)
{
int tmp = search();
if(tmp != -1)
result = Math.min(result,tmp);
return;
}
for(int i=start;i<=n;i++)
{
if(!visit[i])
{
visit[i] = true;
color[i] = 1;
go(i+1,r+1,b);
color[i] = 2;
go(i+1,r,b+1);
color[i] = 0;
visit[i] = false;
}
}
}
static void printColor() {
for (int i = 1; i <= n; i++) {
System.out.print(color[i] + " ");
}
System.out.println();
}
static int search()
{
Queue<Integer> qr = new LinkedList<>();
Queue<Integer> qb = new LinkedList<>();
boolean[] v = new boolean[n+1];
int rsum = 0;
int bsum = 0;
for(int i=1;i<=n;i++)
{
if(color[i] == 1)
{
qr.add(i);
v[i] = true;
rsum += num[i];
break;
}
}
for(int i=1;i<=n;i++)
{
if(color[i] == 2)
{
qb.add(i);
v[i] = true;
bsum += num[i];
break;
}
}
while(!qr.isEmpty())
{
Integer cur = qr.poll();
for(int next : graph[cur])
{
if(!v[next] && color[next] == 1)
{
v[next] = true;
rsum += num[next];
qr.add(next);
}
}
}
while(!qb.isEmpty())
{
Integer cur = qb.poll();
if(!v[cur])
{
v[cur] = true;
bsum += num[cur];
}
for(int next : graph[cur])
{
if(!v[next] && color[next] == 2)
{
v[next] = true;
bsum += num[next];
qb.add(next);
}
}
}
for(int i=1;i<=n;i++)
{
if(!v[i])
{
return -1;
}
}
return Math.abs(rsum - bsum);
}
}