백준 17779 <게리멘더링2>

게리맨더링 주어진 방법보다 어렵게 푼 방식이기 때문에 참고!! 만 하자!

이 문제는 DFS 즉 백트래킹으로 가능한 꼭지점 4개를 구하고 최소의 차이가 나는 값을 출력하는 것이다.

 

문제에서 처럼 푼다면 4중 포문으로 꼭지점의 좌표 d1, d2, 이렇게 구해서 계산을 하면 되겠지만 문제를 이해하고 계산하는 방법이 없다면 푸는 방법이다.

 

DFS를 3번 돌려서 가능하다면 최솟값을 비교해주도록 했다. 

이 그림으로 설명하자면

1. 1의 꼭지점을 잡고 오른쪽 아래로 이동
2. 꼭지점이 가능하다면 왼쪽 아래 대각선으로
3. 이동이 가능하다면 1에서 2까지 온 거리만큼 3위 치에서 좌상 대각선으로 이동하는 문제이다.

이렇게 총 3번의 DFS로 문제를 해결할 수 있다.

 

1번에서 빨간방향으로 한번 이동해서 계산해주고  다시 돌아와 파란색 동그라마 부분에서 아래로 내려가면서 검사하고 이런 흐름으로 검사를 하는 것이다.

 

이렇게 하면 완성할 수 있는 전체 마름모를 다 돌 수 있을 것이다.

len은 d1, d2 두 개를 뜻하는 배열이고, num은 num [4][2]로 각각의 좌표를 넣어주는 역할을 한다.

여기서 sum의 역할은 1번 구역 2번 구역, 3번 구역, 4번 구역을 구해 sum에서 이 값들을 빼면 5번 구영의 값이 나온다.

불필요한 게산을 피해주기 위해 먼저 계산한 것이다.

 

이 부분은 앞에 말했던 DFS를 하는 부분이다. i값이 1이면 시작점에서 오른쪽 아래 대각선으로 가고,

i값이 2 이면 왼쪽 아래 대각선으로 간다.

i가 3이면 len [0]이 d1이기 때문에 그만큼 값을 더해주고 그 값이 경계를 넘어가지 않는다면 계산을 해주는 것이다.

 

이건 첫 번째 영역을 계산하는 부분이다.  이렇게 두 사각형을 따로 계산하는 방식으로 풀었다.

 

이건 두 번째 영역을 계산하는 부분이다.

이건 세 번째 구역을 계산하는 코드이다.

마지막으로 네 번째 구역을 구하는 코드이다.

 

이런 식으로 4가지 구역을 각 계산해서 sum에서 빼줘서 비교를 실행해줬다.

 

실제로 비슷하지만 더 어려웠던 문제를 코딩 테스트에서 쳤기 때문에 가능한 방법이었다.. 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{

	static int n, map[][], len[], num[][], result, dir[][] = { { 1, 1 }, { 1, -1 }, { -1, -1 } }, sum;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(kb.readLine());
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(kb.readLine());
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				sum += map[i][j];
			}
		}
		len = new int[2];
		num = new int[4][2];
		result=Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				num[0][0] = i;
				num[0][1] = j;
				dfs(1);
			}
		}
		System.out.println(result);

	}

	private static void dfs(int i) {
		// TODO Auto-generated method stub
		if (i == 3) {
			for (int j = 0; j < 2; j++) {
				num[i][j] = num[i - 1][j] + dir[i - 1][j]*len[0];
			}
			if (num[i][0] >= 0 && num[i][0] < n && num[i][1] >= 0 && num[i][1] < n) {
				count();
			}
			return;
		}
		for (int j = 0; j < 2; j++) {
			num[i][j] = num[i - 1][j] + dir[i - 1][j];
		}
		len[i - 1] = 0;
		while (num[i][0] >= 0 && num[i][0] < n && num[i][1] >= 0 && num[i][1] < n) {
			len[i - 1]++;
			dfs(i + 1);
			for (int j = 0; j < 2; j++) {
				num[i][j] += dir[i - 1][j];
			}
		}
	}

	private static void count() {
		// TODO Auto-generated method stub
		int sum1[]=new int[5];
		{
			for(int i=0;i<num[0][0];i++) {
				for(int j=0;j<=num[0][1];j++) {
					sum1[0]+=map[i][j];
				}
			}
			int count=0;
			for(int i=num[0][0];i<num[3][0];i++) {
				for(int j=0;j<num[0][1]-count;j++) {
					sum1[0]+=map[i][j];
				}
				count++;
			}

		} // 첫번째
		{
			for(int i=0;i<num[0][0];i++) {
				for(int j=num[0][1]+1;j<n;j++) {
					sum1[1]+=map[i][j];
				}
			}
			int count=1;
			for(int i=num[0][0];i<=num[1][0];i++) {
				for(int j=num[0][1]+count;j<n;j++) {
					sum1[1]+=map[i][j];
				}
				count++;
			}

		} // 두번째
		{
			int count=0;
			for(int i=num[3][0];i<=num[2][0];i++) {
				for(int j=0;j<num[3][1]+count;j++) {
					sum1[2]+=map[i][j];
				}
				count++;
			}
			for(int i=num[2][0]+1;i<n;i++) {
				for(int j=0;j<num[2][1];j++) {
					sum1[2]+=map[i][j];
				}
			}

		} // 세번째
		{
			int count=0;
			for(int i=num[1][0]+1;i<=num[2][0];i++) {
				for(int j=num[1][1]-count;j<n;j++) {
					sum1[3]+=map[i][j];
				}
				count++;
			}
			for(int i=num[2][0]+1;i<n;i++) {
				for(int j=num[2][1];j<n;j++) {
					sum1[3]+=map[i][j];
				}
			}

		} // 네번째
		sum1[4]=sum-sum1[0]-sum1[1]-sum1[2]-sum1[3];
		int max=0;
		int min=Integer.MAX_VALUE;
		for(int i=0;i<5;i++) {
			max=Math.max(max,sum1[i]);
			min=Math.min(min,sum1[i]);
		}
		result=Math.min(result,max-min);
	}

}