[백준_17779번] 게리맨더링 2_삼성 SW 역량테스트

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]를 의미한다.

 

[코드]

import java.util.*;

public class BaekJoon_17779 {
	static int[][] map;
	static int n,total=0,min=Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		map=new int[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				map[i][j]=sc.nextInt();
				total+=map[i][j];
			}
		}
		
		// x,y,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++) {
						// (x+d1+d2 ≤ N)를 벗어난 경우
						if(x+d1+d2>n)
							continue;
						
						// (1 ≤ y-d1), (y+d2 ≤ N)를 벗어난 경우
						if(y-d1<=0||y+d2>n)
							continue;
						
						seperateDistric(x,y,d1,d2);
					}
				}
			}
		}
		
		System.out.println(min);
	}
	static void seperateDistric(int x, int y, int d1, int d2) {
		boolean[][] check=new boolean[n+1][n+1];
		
		/*
		 * 5구역 체크하기 
		 * 
		 * 1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
		 * 4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
		 */
		for(int i=0;i<=d1;i++) {
			check[x+i][y-i]=true;
			check[x+d2+i][y+d2-i]=true;
		}
		
		/*
		 * 5구역 체크하기 
		 * 
		 * 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)
		 */
		for(int i=0;i<=d2;i++) {
			check[x+i][y+i]=true;
			check[x+d1+i][y-d1+i]=true;
		}
		
		int[] people=new int[6]; // 각 구역의 인구수를 저장할 배열
		
		// 1구역의 인구 수 구하기 : 1 ≤ r < x+d1, 1 ≤ c ≤ y
		for(int i=1;i<x+d1;i++) {
			for(int j=1;j<=y;j++) {
				if(check[i][j])
					break;
				
				people[1]+=map[i][j];
			}
		}
		
		// 2구역의 인구 수 구하기 : 1 ≤ r ≤ x+d2, y < c ≤ N
		for(int i=1;i<=x+d2;i++) {
			for(int j=n;j>y;j--) {
				if(check[i][j])
					break;
				
				people[2]+=map[i][j];
			}
		}
		
		// 3구역의 인구 수 구하기 : x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
		for(int i=x+d1;i<=n;i++) {
			for(int j=1;j<y-d1+d2;j++) {
				if(check[i][j])
					break;
				
				people[3]+=map[i][j];
			}
		}
		
		// 4구역의 인구 수 구하기 : x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
		for(int i=x+d2+1;i<=n;i++) {
			for(int j=n;j>=y-d1+d2;j--) {
				if(check[i][j])
					break;
				
				people[4]+=map[i][j];
			}
		}
		
		// 5구역의 인구수는 전체 인구수에서 다른 구역의 인구수를 빼는 방법으로 구한다.
		people[5]=total;
		
		for(int i=1;i<=4;i++)
			people[5]-=people[i];
		
		/*
		 * 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하기 위해
		 * people 배열을 정렬후 배열의 마지막 값에서 첫 번째 값을 뺀 값과 min을 비교하여 갱신한다. 
		 */
		Arrays.sort(people); 
		min=Math.min(min, people[5]-people[1]);
	}
}

 

[고찰]

 이번 문제는 시뮬레이션 문제로 문제에 각 구역의 범위가 다 주어졌기 때문제 여태까지 풀어봤던 삼성 기출문제 중 가장 쉬웠던 문제였다. 문제를 구조화 해보면 아래와 같다.

 

*** 1) 가능한 x, y, d1, d2 경우의 수 모두 구하기(main 함수)

1-1) 4중 for문을 사용하여 주어진 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N) 범위 내에 있는 x, y, d1, d2를 매개변수로 전달하여 seperateDistric 함수를 호출한다.

 

*** 2) 각 구역의 인구 수를 구하기(seperateDistric 함수)

2-1) boolean 배열을 사용하여 5구역에 해당하는 곳을 true로 변경한다.

2-2) 주어진 각 구역의 범위를 사용하여 나머지 구역의 인구 수를 구한다. 각 구역은 5구역을 중심으로 구할 수 있는데 1, 3 구역은 5 구역을 중심으로 → 방향으로 모든 배열 값을 더해주면 되고, 2, 4 구역은 5 구역을 중심으로 ← 방향으로 모든 배열 값을 더해주면 된다.

2-3) 이때 check 배열의 값을 활용하여 탐색하는 인덱스의 check 값이 true라면 탐색을 종료한다. 그 이유는 탐색 범위의 끝에 도달하기 이전에 check 배열의 true 값을 만난다면 그 이후부터는 5구역과, 다른 구역에 해당하기 때문에 더 이상 탐색할 이유가 없기 때문이다.

2-4) 각 구역의 인구 수를 모두 구했다면 전체 인구수에서 각 구역의 인구 수를 빼 5구역의 인구 수를 구하고, 모든 구역의 인구 수를 정렬하여 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해 min 값을 갱신한다.

 

 이번 문제는 문제 내에 배열의 범위가 모두 주어졌기 때문에 쉽게 느껴졌다. 만약 범위가 주어지지 않았다면 어렵게 느껴졌을 것 같은 문제이기도 하다.