https://www.acmicpc.net/problem/17779
17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름
www.acmicpc.net
문제
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
선거구를 나누는 방법은 다음과 같다.
- 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
- 다음 칸은 경계선이다.
- (x, y), (x+1, y-1), ..., (x+d1, y-d1)
- (x, y), (x+1, y+1), ..., (x+d2, y+d2)
- (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
- (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
- 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
- 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
- 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
- 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
- 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
- 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.
| x = 2, y = 4, d1 = 2, d2 = 2 | x = 2, y = 5, d1 = 3, d2 = 2 | x = 4, y = 3, d1 = 1, d2 = 1 |
구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.
입력
첫째 줄에 재현시의 크기 N이 주어진다.
둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.
출력
첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.
제한
- 5 ≤ N ≤ 20
- 1 ≤ A[r][c] ≤ 100
풀이
풀이 1. 초기의 내 풀이
문제를 조금 보다보면, '그림 그려서 구역 나누는 거보다 주어진 조건식만 써서 구역 나누는게 편하다'는 느낌이 온다. 이를 구현하여, 조건식대로 4중 for문을 돌려 x, y, d1, d2를 구하고, 해당 (x, y, d1, d2)에 따라 2중 for문을 돌려 (r, c)를 구역 1,2,3,4,5중 하나로 나누면 된다. 즉, 6중 for문 문제이다.
다만, 나는 처음에 조건식대로 구역 1, 2, 3, 4를 나누고 나머지는 구역 5가 된다고 생각했는데, (당연히) 아니다! 이래서 문제를 잘 읽을 필요가 있다. 따라서, 문제 조건 순서대로 경계 및 경계 내부 처리를 하기 위해 경계는 for문 4번 사용하여 칠해주고, 경계 내부는 경계 내부의 점 하나((x+1, y)는 무조건 들어간다)를 큐에 넣어서 BFS를 수행하였다. 다만, d1 == 1 or d2 == 1 인 경우, 경계 내부는 서로 연결되어 있지 않고 끊어져 있다(문제의 예시 3을 보면 이해가 갈 것이다.): 따라서, (x+i+1, y+i) (0<=i<=d2), (x+i+1, y-i) (0<=i<=d1)을 모두 queue에 넣어줘서 bfs를 실행했다. 이후, 경계 및 경계 내부이면 조건식을 만족해도 구역 1, 2, 3, 4로 잘못 판단하는 일이 없어졌다.
...위 문단을 열심히 읽어봤다면, '이게 뭔 소리지?' 싶을 것이다. 맞다..초기 설계에서 고려하지 못한 사항을 급하게 개선하겠다고 풀이가 더러워졌다. 초기 설계를 확실하게 하고, 문제를 잘 읽을 필요가 있다.
풀이 2. 경계를 판단하여 바로 풀기 (https://www.acmicpc.net/source/42544621 참고)
각 구역 조건마다 '경계 밖인 조건(구역마다 다르다.)'을 구하여 추가하면 된다. 조건이 살짝 헷갈리기도 하는데, 공책 하나 챙겨두고 차분히 그려보면 조건을 찾을 수 있다. BFS 안 돌기에 시간도 훨씬 덜 걸린다.
시간 복잡도 이야기
6중 for문이고 N <= 20 이므로 대략 6400만 정도의 단위 연산이 수행되지만, (x, y, d1, d2)를 구하는 4중 for문은 조건에 따라 제외되는 경우가 좀 있어서 그렇게 많이 연산이 이루어지진 않는다.살짝 느낌이 쎄했는데, 다른 풀이가 떠오르지도 않았기에 6중 for문으로 풀었고 맞았다.
다 풀고나서, 심심해서 N=20일 때 단위 연산 횟수를 찍어봤는데 4332000이 나온다: 예외 처리가 꽤 많이 된다.
코드
코드 1. 초기 풀이(볼 필요 없다)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int ans = Integer.MAX_VALUE, N;
static int[] areas; // areas[i]: i+1번째 구역
static int[][] city = new int[N+1][N+1];
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
city = new int[N+1][N+1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
city[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
System.out.println(ans);
}
static void solve() {
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
for (int d1 = 1; d1 <= y-1; d1++) {
for (int d2 = 1; d2 <= Math.min(N-y, N-x-d1); d2++) {
areas = new int[5];
calc(x, y, d1, d2);
}
}
}
}
}
static void calc(int x, int y, int d1, int d2) {
int[][] divide = new int[N+1][N+1];
// 경계 구하기
for (int i = 0; i <= d1; i++) {
divide[x+i][y-i] = 5;
}
for (int i = 0; i <= d2; i++) {
divide[x+i][y+i] = 5;
}
for (int i = 0; i <= d2; i++) {
divide[x+d1+i][y-d1+i] = 5;
}
for (int i = 0; i <= d1; i++) {
divide[x+d2+i][y+d2-i] = 5;
}
// 내부값들 넣어주기
Queue<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < d2; i++) {
queue.offer(new int[] {x+1+i, y+i});
divide[x+1+i][y+i] = 5;
}
for (int i = 0; i < d1; i++) {
queue.offer(new int[] {x+1+i, y-i});
divide[x+1+i][y-i] = 5;
}
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int r = temp[0], c = temp[1];
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
// 구조적으로 (nr, nc)가 범위를 벗어나진 않는다.
if (divide[nr][nc] == 5) continue;
divide[nr][nc] = 5;
queue.offer(new int[] {nr, nc});
}
}
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
// 경계 or 경계 내부이면 구역 5에 인구 더하고 바로 다음 for문 실행
if (divide[r][c] == 5) {
areas[4] += city[r][c];
continue;
}
if (r < x+d1) {
if (c <= y) {
areas[0] += city[r][c];
continue;
}
} else {
if (c < y-d1+d2) {
areas[2] += city[r][c];
continue;
}
}
if (r <= x+d2) {
if (c > y) {
areas[1] += city[r][c];
continue;
}
} else {
if (c >= y-d1+d2) {
areas[3] += city[r][c];
continue;
}
}
areas[4] += city[r][c];
}
}
Arrays.sort(areas);
ans = Math.min(ans, areas[4] - areas[0]);
}
}
코드 2: 구역 1, 2, 3, 4 체크와 경계 체크를 동시에 하는 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int ans = Integer.MAX_VALUE, N;
static int[] areas;
static int[][] city = new int[N+1][N+1];
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
city = new int[N+1][N+1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
city[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
System.out.println(ans);
}
static void solve() {
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
for (int d1 = 1; d1 <= y-1; d1++) {
for (int d2 = 1; d2 <= Math.min(N-y, N-x-d1); d2++) {
areas = new int[5];
calc(x, y, d1, d2);
}
}
}
}
}
static void calc(int x, int y, int d1, int d2) {
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (r < x+d1) {
// 첫 번째 구역의 경계 조건 == 'c < y-r+x'
if (c <= y && c < y-r+x) {
areas[0] += city[r][c];
continue;
}
} else {
if (c < y-d1+d2 && c < y+r-x-2*d1) {
areas[2] += city[r][c];
continue;
}
}
if (r <= x+d2) {
if (c > y && c > y+r-x) {
areas[1] += city[r][c];
continue;
}
} else {
if (c >= y-d1+d2 && c > y-r+x+2*d2) {
areas[3] += city[r][c];
continue;
}
}
areas[4] += city[r][c];
}
}
Arrays.sort(areas);
ans = Math.min(ans, areas[4] - areas[0]);
}
}
* 코드 3: 경계만 그리고 for문에서 적당히 break하여 구역 1, 2, 3, 4, 5를 그리는 코드
(https://sujin7837.tistory.com/413 참고)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static BufferedReader br;
private static StringTokenizer st;
private static int N, min, max, result;
private static int [][]map, garim;
public static void main(String[] args) throws NumberFormatException, IOException {
br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
map=new int[N+1][N+1];
for(int r=1;r<=N;r++) {
st=new StringTokenizer(br.readLine());
for(int c=1;c<=N;c++) {
map[r][c]=Integer.parseInt(st.nextToken());
}
}
result=Integer.MAX_VALUE;
for(int r=1;r<=N;r++) {
for(int c=1;c<=N;c++) {
for(int d1=1;d1+r<N;d1++) {
if(d1+1>c) continue;
for(int d2=1;d2+d1+r<=N;d2++) {
if(d2+c>N) continue;
garim=new int[N+1][N+1];
garimendering(r, c, d1, d2); // 기준점 : (r, c), 경계의 길이 : d1, d2
min=Integer.MAX_VALUE;
max=Integer.MIN_VALUE;
for(int i=1;i<=5;i++) { // 1~5번 선거구의 인구 수를 각각 구함
int get=population(i);
min=Math.min(min, get); // 선거구 인구의 최솟값
max=Math.max(max, get); // 선거구 인구의 최댓값
}
result=Integer.min(result, max-min); // 선거구 인구 (최댓값-최솟값)의 최솟값
}
}
}
}
System.out.println(result);
}
private static void garimendering(int x, int y, int d1, int d2) {
int R=x;
int C=y;
while(R<=x+d1) { // 경계 1번
garim[R][C]=5;
R++;
C--;
}
R=x;
C=y;
while(R<=x+d2) { // 경계 2번
garim[R][C]=5;
R++;
C++;
}
R=x+d1;
C=y-d1;
while(R<=x+d1+d2) { // 경계 3번
garim[R][C]=5;
R++;
C++;
}
R=x+d2+d1;
C=y+d2-d1;
while(R>=x+d2) { // 경계 4번
garim[R][C]=5;
R--;
C++;
}
for(int r=1;r<x+d1;r++) { // 선거구 1
for(int c=1;c<=y;c++) {
if(garim[r][c]==0) garim[r][c]=1;
else break;
}
}
for(int r=1;r<=x+d2;r++) { // 선거구 2
for(int c=N;c>=y+1;c--) {
if(garim[r][c]==0) garim[r][c]=2;
else break;
}
}
for(int r=x+d1;r<=N;r++) { // 선거구 3
for(int c=1;c<y-d1+d2;c++) {
if(garim[r][c]==0) garim[r][c]=3;
else break;
}
}
for(int r=N;r>x+d2;r--) { // 선거구 4
for(int c=N;c>=y-d1+d2;c--) {
if(garim[r][c]==0) garim[r][c]=4;
else break;
}
}
for(int r=x;r<=x+d1+d2;r++) { // 선거구 5
for(int c=y-d1;c<=y+d2;c++) {
if(garim[r][c]==0) garim[r][c]=5;
}
}
}
private static int population(int x) { // 선거구 x의 인구 수
int cnt=0;
for(int r=1;r<=N;r++) {
for(int c=1;c<=N;c++) {
if(garim[r][c]==x) cnt+=map[r][c];
}
}
return cnt;
}
private static boolean isIn(int r, int c) {
return r>=0 && r<N && c>=0 && c<N;
}
}출처: https://sujin7837.tistory.com/413 [sujin's 개발 로그:티스토리]
실행 결과
풀이 2는 풀이 1과 다르게, 4중 for문 내에서 매번 BFS를 돌 이차원 배열을 만들지 않으며, BFS를 돌지도 않는다. 이에, 풀이 2가 풀이 1보다 2배 이상 빠른 것을 알 수 있다:
'PS > Implementation' 카테고리의 다른 글
| 백준 25239번: 가희와 카오스 파풀라투스 (Java) (0) | 2022.06.09 |
|---|---|
| 백준 20056번: 마법사 상어와 파이어볼 (JAVA) (0) | 2022.06.08 |
| 백준 19238번: 스타트 택시 (JAVA) (0) | 2022.05.17 |
| 백준 21608번: 상어 초등학교 (JAVA) (0) | 2022.05.17 |
| 백준 14891번: 톱니바퀴 (JAVA) (0) | 2022.04.13 |