[백준] 17779번: 게리맨더링2 문제 풀이

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

문제 접근 방식

재현시에 5번 선거구의 경계선을 먼저 표시해준다. 이 때, d1과 d2에 따라 선거구의 모양과 크기가 정해지는데, 선거구의 조건은 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 이다.

수학에 약하다보니 d1과 d2를 구하기 위한 조건식에 맞게 d1과 d2를 구하는 과정이 너무 번거롭고 복잡해서 조금 더 쉬운 방법을 찾아보았다.

1~N 사이의 2개의 순열을 구해서, 두 숫자가 위의 조건식을 만족하는 순열일 때에만 다음 단계로 진행하였다.

구해진 d1,d2에 맞게 5번 선거구 경계선을 먼저 그려주고, 각 1,2,3,4번의 경계선을 표시해주었다.
그 후에 dfs로 선거구 번호들을 채워주고, 각 선거구의 최댓값과 최솟값을 구해준다.

중복 순열 구하기

d1과 d2의 순열을 구하기 위해 기저조건을 cnt==2로 해준다.
순열을 구하고 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 조건에 맞다면 다음 단계로 진행한다.
이 때 d1과 d2의 길이가 같은 경우도 있기 때문에 중복 순열로 구했어야했는데, 습관적으로 방문체크를 해서 일반 순열을 구하는 바람에 한참동안이나 틀린 이유를 못 찾고 있었다...
하필이면 문제 예제가 다 맞아서... 진작에 맞출 수 있던걸 계속 붙잡고 있었던 난 바보였다.

static void perm(int cnt) {
	if (cnt == 2) {
		int d1 = perm[0];
		int d2 = perm[1];
		
		for (int y=1; y<=N; y++) {
			for (int x=1; x<=N; x++) {
				if (x<x+d1+d2&&x+d1+d2<=N&&1<=y-d1&&y+d2<=N) {
					v = new int [N+1][N+1];
					draw(y, x, d1, d2);
					dfs(1, 1, 1);
					dfs(1, N, 2);
					dfs(N, 1, 3);
					dfs(N, N, 4);
					ans = Math.min(ans, getPopulationGap());
				}
			}
		}
		return;
	}
		
	for (int i=1; i<N; i++) {
		perm[cnt] = i;
		perm(cnt + 1);
	}
}

각 선거구 선거구 경계선 그리기

각 좌표와 d1, d2에 따라 5번 선거구의 경계선을 먼저 그려주고, 나머지 선거구의 경계선을 그려준다.

위과 같은 모양이 된다. (배열의 크기는 N+1 x N+1이기 때문에 각 0번행열은 제외)

static void draw(int y, int x, int d1, int d2) {
	for (int i=0; i<=d1; i++) { // 5번 선거구 d1 경계선
		v[y-i][x+i] 	 = 5;
		v[y+d2-i][x+d2+i]= 5;
	}
	for (int i=0;i<=d2; i++) { // 5번 선거구 d2 경계선
		v[y+i][x+i] 	 = 5;
		v[y-d1+i][x+d1+i]= 5;
	}
	for (int i=y-d1-1; i>0; i--) 	v[i][x+d1] 	 = 1; // 1번 선거구 경계선
	for (int i=x+d1+d2+1; i<=N; i++)v[y-d1+d2][i]= 2; // 2번 선거구 경계선
	for (int i=x-1; i>0; i--) 		v[y][i] 	 = 3; // 3번 선거구 경계선
	for (int i=y+d2+1; i<=N; i++) 	v[i][x+d2] 	 = 4; // 4번 선거구 경계선
}

선거구 번호 별로 내부 채우기

dfs 혹은 bfs를 통해서 다른 경계선을 만날 때 까지 해당하는 선거구의 번호를 채워준다.
1번 선거구의 같은 경우 (1, 1)좌표에서 시작하고, 2번 선거구는 (1, N)에서 탐색을 시작한다.

위와 같은 모양을 만들어준다.

static void dfs(int y, int x, int n) {
	v[y][x] = n;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0<ny&&ny<=N&&0<nx&&nx<=N&&v[ny][nx]==0)
			dfs(ny, nx, n);
	}
}

...
dfs(1, 1, 1); // 1번 선거구
dfs(1, N, 2); // 2번 선거구
dfs(N, 1, 3); // 3번 선거구
dfs(N, N, 4); // 4번 선거구

인구수 최대값, 최소값 구하기

선거구를 모두 표시했으면, 한칸씩 검사하면서 인구수의 합을 구해준다.
5개 선거구의 인구수를 모두 구했다면 각각 최대 최소값을 구한 뒤, 그 차이를 리턴한다.

static int getPopulationGap() {
	int min = Integer.MAX_VALUE;
	int max = 0;
	int [] p = new int[5];
	for (int i=1; i<=N; i++) {
		for (int j=1; j<=N; j++) {
			if (v[i][j]==1)		p[1]+=arr[i][j]; // 1번 선거구 인구수
			else if (v[i][j]==2)p[2]+=arr[i][j]; // 2번 선거구 인구수
			else if (v[i][j]==3)p[3]+=arr[i][j]; // 3번 선거구 인구수
			else if (v[i][j]==4)p[4]+=arr[i][j]; // 4번 선거구 인구수
			else 				p[0]+=arr[i][j]; // 5번 선거구 인구수
		}
	}
	for (int i=0; i<5; i++) { // 최대, 최소값 비교
		min = Math.min(min, p[i]);
		max = Math.max(max, p[i]);
	}
	return (max-min);
}

회고

계산식이 매우 복잡해서 구현하는 데에 애를 많이 먹었지만 순열 실수만 하지 않았다면 충분히 풀 수 있었을 것 같다.
d1과 d2의 순열이 어떻게 만들어졌는지 확실하게 결과를 먼저 체크하고 다음 단계로 진행을 했어야 했는데, 개인적으로 너무 아쉽다는 생각이 들었다 ㅠㅠ

전체 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, ans = Integer.MAX_VALUE;
	static int [][] arr;
	static int [][] v;
	static int perm [] = new int [2];
	static int [] dy = {-1, 1, 0, 0};
	static int [] dx = {0, 0, -1, 1};

	static int getPopulationGap() {
		int min = Integer.MAX_VALUE;
		int max = 0;
		int [] p = new int[5];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				if (v[i][j]==1)		p[1]+=arr[i][j];
				else if (v[i][j]==2)p[2]+=arr[i][j];
				else if (v[i][j]==3)p[3]+=arr[i][j];
				else if (v[i][j]==4)p[4]+=arr[i][j];
				else 				p[0]+=arr[i][j];
			}
		}
		for (int i=0; i<5; i++) {
			min = Math.min(min, p[i]);
			max = Math.max(max, p[i]);
		}
		return (max-min);
	}
	
	static void dfs(int y, int x, int n) {
		v[y][x] = n;
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0<ny&&ny<=N&&0<nx&&nx<=N&&v[ny][nx]==0)
				dfs(ny, nx, n);
		}
	}
	
	static void draw(int y, int x, int d1, int d2) {
		for (int i=0; i<=d1; i++) {
			v[y-i][x+i] 	 = 5;
			v[y+d2-i][x+d2+i]= 5;
		}
		for (int i=0;i<=d2; i++) {
			v[y+i][x+i] 	 = 5;
			v[y-d1+i][x+d1+i]= 5;
		}
		for (int i=y-d1-1; i>0; i--) 	v[i][x+d1] 	 = 1;
		for (int i=x+d1+d2+1; i<=N; i++)v[y-d1+d2][i]= 2;
		for (int i=x-1; i>0; i--) 		v[y][i] 	 = 3;
		for (int i=y+d2+1; i<=N; i++) 	v[i][x+d2] 	 = 4;
	}
	
	static void perm(int cnt) {
		if (cnt == 2) {
			int d1 = perm[0];
			int d2 = perm[1];
			
			for (int y=1; y<=N; y++) {
				for (int x=1; x<=N; x++) {
					if (x<x+d1+d2&&x+d1+d2<=N&&1<=y-d1&&y+d2<=N) {
						v = new int [N+1][N+1];
						draw(y, x, d1, d2);
						dfs(1, 1, 1);
						dfs(1, N, 2);
						dfs(N, 1, 3);
						dfs(N, N, 4);
						ans = Math.min(ans, getPopulationGap());
					}
				}
			}
			return;
		}
		
		for (int i=1; i<N; i++) {
			perm[cnt] = i;
			perm(cnt + 1);
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = 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++) arr[i][j] = Integer.parseInt(st.nextToken());
		}

		perm(0);
		System.out.println(ans);
	}

}