[JAVA] BOJ(백준) - 게리맨더링 2 - 17779

문제내용

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

17779번: 게리맨더링 2

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 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인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

---

문제풀이

오랜만에 삼성역량기출문제를 풀어봤다.

까보면 별거 없는 문젠데 범위를 가지고 놀아야되는 부분이 익숙하지 않아서 생각보다 오래걸린 문제다.

각설하고 풀이는 다음과 같은 과정을 거친다.

 

1. x, y, d1, d2가 될수 있는 모든 경우의 수를 구한다. ( 4중 for문, 완탐 ) -> 경우의수 하나마다 아래과정을 실행.

2. map 배열에 경계를 표시해준다. 이때 각 경계마다 반복문으로 표시해줌.

3. 경계구역 외에 1,2,3,4 번 구역을 표시해준다.

4. 1차원 배열에 1,2,3,4,5 번 구역의 인원수를 넣어준다.

5. 배열 정렬후 min = Math.min(min, 배열 최댓값 - 배열 최솟값) 으로 최종값을 갱신해준다.

 

간단한게 말하면 위의 과정을 거쳐서 문제를 풀수 있다.

자세하게 써놓지 않은 이유는 범위를 가지고 경계를 표시하고 경계 구역외에 1,2,3,4 번 구역을 표시하는건 그냥 구현 부분이라 코드를 보거나 직접 생각해보는게 더 빠르다고 생각하기 때문..

 

코드를 보자.

 

---

코드

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, min;
	static int[][] A;
	static int[][] map;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		A = new int[n+1][n+1];
		min = Integer.MAX_VALUE; 
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Queue<Node> idx = new LinkedList<>();//x, y
		Queue<Node> line = new LinkedList<>();//d1, d2
		for(int x=1; x<=n; x++) {
			for(int y=1; y<=n; y++) {
				for(int d1=1; d1<=n; d1++) {
					for(int d2=1; d2<=n; d2++) {
						if(x+d1+d2>n) continue;
						else if(y-d1<1 || y+d2>n) continue;
						idx.add(new Node(x,y)); //문제에서 주어진 범위 활용
						line.add(new Node(d1,d2)); //문제엣 주어진 범위 활용
					}
				}
			}
		}
		
		while(!idx.isEmpty()) {
			int x = idx.peek().x, y = idx.poll().y;
			int d1 = line.peek().x, d2 = line.poll().y;
			
			map = new int[n+1][n+1];
			
			//경계구역 표시하기, 5로 표시.
			int num=0, px=x, py=y;
			while(num<=d1) { //2-1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
				map[px][py] = 5;
				px=x+num;
				py=y-num;
				num++;
			}
			num=0;
			px=x;
			py=y;
			while(num<=d2) { //2-2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
				map[px][py] = 5;
				px=x+num;
				py=y+num;
				num++;
			}
			num=0;
			px=x+d1;
			py=y-d1;
			while(num<=d2) { //2-3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
				map[px][py] = 5;
				px = x+d1+num;
				py = y-d1+num;
				num++;
			}
			num=0;
			px=x+d2;
			py=y+d2;
			while(num<=d1) { //2-4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
				map[px][py] = 5;
				px = x+d2+num;
				py = y+d2-num;
				num++;
			}
			map[px][py] = 5;
			
			
			bfs(1,x+d1-1,1,y,1); //1번 구역
			bfs(1,x+d2,y+1,n,2); //2번 구역
			bfs(x+d1,n,1,y-d1+d2-1,3); //3번 구역
			bfs(x+d2+1,n,n,n,4); //4번 구역
			
			min = Math.min(min, people());
		}
		System.out.println(min);
	}
	
	public static void bfs(int x1, int x2, int y1, int y2, int num) {
		Queue<Node> q = new LinkedList<>();
		boolean[][] check = new boolean[n+1][n+1];
		q.add(new Node(x1,y1));
		check[x1][y1] = true;
		if(map[x1][y1]==0) map[x1][y1] = num;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				
				//배열범위 밖으로 넘어가거나, 경계값 넘어가면 무시
				if(nx<1 || ny<1 || nx>n || ny>n || nx>x2 || ny>y2) continue;
				
				if(!check[nx][ny] && map[nx][ny]==0) {
					q.add(new Node(nx,ny));
					check[nx][ny] = true;
					map[nx][ny] = num;
				}
			}
		}
	}
	
	//최대최소값 차이구하기.
	public static int people() {
		int diff=0;
		int[] nums = new int[5];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j]==1) nums[0]+=A[i][j];
				if(map[i][j]==2) nums[1]+=A[i][j];
				if(map[i][j]==3) nums[2]+=A[i][j];
				if(map[i][j]==4) nums[3]+=A[i][j];
				if(map[i][j]==5 || map[i][j]==0) nums[4]+=A[i][j];
			}
		}
		Arrays.sort(nums);
		diff = nums[4]-nums[0];
		return diff;
	}
}

---

마치며

다른사람들 풀이도 봤는데 일단 내가 푼거보다는 간단하게 푼걸 볼 수 있다. 예를들어 구역을 표시하는것도 bfs가 아닌 그냥 for문으로 표시한다던지... (범위가 어디부터 어디까진지 알기에 가능)

하지만 이문제에선 어찌됐든 x,y,d1,d2를 어떻게 구하고, 경계값을 어떻게 표시할지 아는게 더 중요하다고 생각한다.