[백준] 17471번:게리맨더링 (Java 자바)

[백준] 17471번:게리맨더링 (Java 자바)

반응형

문제

https://www.acmicpc.net/problem/17471

풀이 및 소스코드

1. 조합으로 선거구 묶음 구하기 1개+n-1개, 2개+n-2개 이런식으로 나눠줌

for(int i=1;i<=n/2;i++) { permu(0, 0, i); }

2. 하나의 경우의 수가 완성이 되면, bfs를 통해서 서로 연결된 선거구인지 확인한다.

두 그룹 다 비교해준다.

Queue q; boolean[] v; q = new LinkedList<>(); v = new boolean[n]; q.add(s.get(0)); v[s.get(0)] = true; int count = 1; while(!q.isEmpty()) { int a = q.poll(); for(int b:g[a]) { if(!v[b]&&s.contains;(b)) { //b를 방문하지 않았고, s에 b가 포함되어있다면 q.add(b); v[b]=true; count++; } } } if(count!=s.size()) return; LinkedList ns = new LinkedList<>(); for(int i=0;i(); v = new boolean[n]; q.add(ns.get(0)); v[ns.get(0)] = true; count = 1; while(!q.isEmpty()) { int a = q.poll(); for(int b:g[a]) { if(!v[b]&&ns.contains;(b)) { //b를 방문하지 않았고, ns에 b가 포함되어있다면 q.add(b); v[b]=true; count++; } } } if(count!=ns.size()) return;

3. 인구수 차이 비교

int po1 = 0; int po2 = 0; for(int i=0;i

전체 코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int n; static LinkedList[] g; static LinkedList s = new LinkedList<>(); static int res = Integer.MAX_VALUE; static int[] po; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; n = Integer.parseInt(br.readLine()); po = new int[n]; st = new StringTokenizer(br.readLine()); for(int i=0;i(); st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); for(int j=0;j q; boolean[] v; q = new LinkedList<>(); v = new boolean[n]; q.add(s.get(0)); v[s.get(0)] = true; int count = 1; while(!q.isEmpty()) { int a = q.poll(); for(int b:g[a]) { if(!v[b]&&s.contains;(b)) { //b를 방문하지 않았고, s에 b가 포함되어있다면 q.add(b); v[b]=true; count++; } } } if(count!=s.size()) return; LinkedList ns = new LinkedList<>(); for(int i=0;i(); v = new boolean[n]; q.add(ns.get(0)); v[ns.get(0)] = true; count = 1; while(!q.isEmpty()) { int a = q.poll(); for(int b:g[a]) { if(!v[b]&&ns.contains;(b)) { //b를 방문하지 않았고, ns에 b가 포함되어있다면 q.add(b); v[b]=true; count++; } } } if(count!=ns.size()) return; //여기까지 왔으면 서로 연결되어있는 선거구라는 뜻! //이제는 인구비교 int po1 = 0; int po2 = 0; for(int i=0;i

반응형

from http://jainn.tistory.com/282 by ccl(A) rewrite - 2021-09-27 23:00:56