[17779] 게리맨더링 2

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

17779번: 게리맨더링 2

---

2019 삼성 하반기 공채 코딩테스트 문제입니다. 저도 실제로 시험장에 가서 풀었던 두 문제중 한개였는데, 이 문제에 3시간을 모두 투자했지만 못풀었습니다ㅠㅠ. 저는 2차원 배열에서 4개를 뽑는 모든 경우의 수를 보면서 5개의 선거구를 나눌려고 시도해봤는데 그렇게 풀면 당연히 시간초과가 발생하고, 어찌어찌해서 4개를 뽑아서 연결시켰지만 선거구를 5개를 나누는 과정도 문제를 꼼꼼하게 읽지 않은 탓에 나누지 못했습니다. 제가 실력이 많이 부족해서 못푼것을 인정해서 개인적으로 미련도 안남았던 시험 같습니다.

SWEA 에 디저트 카페라는 문제도 게리멘더링2 와 똑같이 2차원 배열에서 4개의 숫자를 뽑는 거였는데, 디저트 카페를 건드려봤더라면 게리멘더링2도 풀 수 있지 않았을까 아쉬움이 많이 남고, 다음에는 문제를 더 많이 풀고 꼼꼼하게 정리해서 하반기 코딩테스트와 같은 일이 안일어나도록 노력해야 겠다고 생각했습니다.

 

이 문제에서 풀 기 위해서는 먼저 가장 위에 꼭지점이 될 수 있는 점을 정해야 합니다. 

설명을 쉽게하기 위해서 왼쪽 처럼 각 꼭지점을 1~4번 이라고 정하고,

1번부터 2번까지의 길이를 d1, 1번부터 3번까지의 길이를 d2 라고 정합니다.

4중 for 문을 이용해서 1번 꼭지점의 x, y좌표와 d1, d2길이가 정해지면 2, 3번점을 정할 수 있고,

2, 3번점 에서 d1과 d2를 이용해서 4번점을 구할 수 있습니다.

 

 

① 1번 점의 좌표(x, y)를 구하는 2중 for문은 2번과 3번의 점을 정해줘야 하기 때문에 0, N-1 번째 열에 위치할 수 없고, 4번 점을 정해줘야 하기 때문에  N-2, N-1 번째 행에 위치할 수 없습니다.

② 1번 점의 좌표(x, y) 와 d1이 정해지면 2번점의 좌표 (x+d1, j-d1) 를 구할 수 있습니다.

③ 1번 점의 좌표(x, y) 와 d2가 정해지면 3번점의 좌표 (x+d2, j+d2) 를 구할 수 있습니다.

④ 2번 점의 좌표 (x+d1, j-d1), 3번 점의 좌표 (x+d2, j+d2) 가 정해지면 4번점의 좌표(i+d2+d1, j-d1+d2) 를 구할 수 있습니다.

⑤ 1번 점의 좌표와 d1, d2 가 정해지면 2, 3, 4번 점이 배열 범위를 벗어나지 않는지 체크해야 합니다.

 

그리고 구역 번호를 쉽게 붙이는 방법은 5번 구역을 제외한 나머지 1~4번 구역들이 4개의 꼭지점을 기준으로 나누어져있기 때문에 처음 2차원 배열의 초기값들을 0이 아닌 5로 초기화 시키면 좀 더 쉽게 구역을 나눌 수 있습니다.

 

[ 문제 풀이 ]

1. 위에서 설명 했던 방법으로 4개의 꼭지점의 좌표를 정합니다.

2. numbering() 이라는 함수는 4개의 꼭지점을 중심으로 5개의 구역의 번호를 붙이는 것입니다. 

3. 구역에 1~5번까지 번호를 붙였다면, calc() 라는 함수로 각 번호에서 DFS를 통해 구역별로 인구수를 results라는 1차원 배열에 저장하고 최댓값과 최솟값의 차이를 answer 라는 ArrayList에 저장합니다.

4. 그럼 최종적으로 모든 경우에서 answer 라는 ArrayList에 나누어진 구역의 최댓값과 최솟값의 차가 저장되어 있기 때문에 정렬을 하고 최솟값을 출력합니다.

---

// 백준 17779	

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	static int N;
	static int[] results;
	static int[][] map, numMap, dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};
	static ArrayList<Point> list;
	static boolean[][] visited;
	static ArrayList answer = new ArrayList();
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();

		map = new int[N][N];
		list = new ArrayList<Point>();

		for(int i=0; i<4; i++) {
			list.add(new Point(0, 0));
		}
		
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				map[i][j] = sc.nextInt();

		for (int i = 0; i < N-2; i++) {
			for (int j = 1; j < N - 1; j++) {
				for (int d1 = 1; d1 <= j; d1++) {
					for (int d2 = 1; d2 < N - j; d2++) {
						
						if(isInside(i+d1, j+d2) && isInside(i+d2+d1, j-d1+d2)) {
							list.set(0, new Point(i, j));
							list.set(1, new Point(i+d1, j-d1));
							list.set(2, new Point(i+d2, j+d2));
							list.set(3, new Point(i+d2+d1, j-d1+d2));
							
							
							numbering();
							calc();
						} 
					}
				}
			}
		}
		
		Collections.sort(answer);
		System.out.println(answer.get(0));
	}
	
	public static void calc() {
		results = new int[6];
		visited = new boolean[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(!visited[i][j]) DFS(i, j, numMap[i][j]);
			}
		}
		
		int min = 999999999;
		int max = -999999999;
		
		for(int i=1; i<=5; i++) {
			if(min > results[i]) min = results[i];
			if(max < results[i]) max = results[i];
		}
		
		answer.add(max-min);
	}
	
	public static void DFS(int x, int y, int value) {
		
		results[value] += map[x][y];
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];
			
			if(isInside(nx, ny) && !visited[nx][ny] && numMap[nx][ny] == value) {
				DFS(nx, ny, value);
			}
		}
	}
	
	public static void numbering() {
		numMap = new int[N][N];
		
		for(int i=0; i<N; i++) 
			for(int j=0; j<N; j++) 
				numMap[i][j] = 5;
		
		Point p1 = list.get(0);
		Point p2 = list.get(1);
		Point p3 = list.get(2);
		Point p4 = list.get(3);
		
		// 1번 구역
		int temp = 0;
		for(int i=0; i<p2.x; i++) {
			if(i >= p1.x) temp++;
			for(int j=0; j<=p1.y-temp; j++) {
				numMap[i][j] = 1;
			}
		}
		
		
		// 2번 구역
		temp = 0;
		for(int i=0; i<=p3.x; i++) {
			if(i>p1.x) temp++;
			for(int j=p1.y+1+temp; j<N; j++) {
				numMap[i][j] = 2;
			}
		}
		
		// 3번 구역
		temp = 0;
		for(int i=N-1; i>=p2.x; i--) {
			if(i < p4.x) temp++;
			for(int j=0; j<p4.y-temp; j++) {
				numMap[i][j] = 3;
			}
		}
		
		// 4번 구역
		temp = 0;
		for(int i=N-1; i>p3.x; i--) {
			if(i <= p4.x) temp++;
			for(int j=p4.y+temp; j<N; j++) {
				numMap[i][j] = 4;
			}
		}
		
	}
	public static boolean isInside(int x, int y) {
		return x>=0 && y>=0 && x<N && y<N;
	}
}

class Point {
	int x;
	int y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
}