[백준] 17779.게리맨더링2 (java) / BackTracking, DFS, 시뮬레이션, 완전탐색

@BackTracking, DFS, 시뮬레이션, 완전탐색 / 4h 이상 (디버깅만 3시간 한 듯)

SWEA 2105.디저트 카페 ( 포스팅 ) 와 비슷한 문제처럼 보여서 쉽겠거니 하고 풀었는데,

테케조차 계속 틀리게 나와서 디버깅하느라 너무 힘들었다..ㅠ

풀고나서 다시 보니 너무 어렵게 생각했던 것 같다.

그래도 백트래킹 공부하기에는 좋은 문제인 듯..

 

 

문제 링크

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

17779번: 게리맨더링 2

 

 

삽질 포인트

1. 처음에는 각 변의 길이를 다 들고 다니면서,

마주보고 있는 변의 길이가 같은지를 체크했는데

사실 변의 길이는 d1, d2 이 두개만 들고다니면 된다.

어차피 평행한 변의 길이가 같지 않으면, 종료 조건에 부합하지 않아서, 자동으로 무시된다.

 

 

2. 가장 큰 문제는, visit을 사용했을 때 뜬금없는 곳이 지워지는 것이었다

디버깅을 해 보니, 이렇게 사각형이 그려진 후,

다음 사각형이 그려질 때 파란 동그라미 부분이 지워졌다.

 

차라리 빨간 점이 지워졌으면 이해라도 하겠는데, 도저히 알 수가 없어서 visit 배열을 단계별로 출력해보니

이런 모양으로 다음 사각형이 그려졌다가, 조건을 충족하지 못해서 지워지는 과정에서

저 동그라미 친 5를 지우는 것이었다..ㅎㅎ

 

 

해결 방법

그래서 nx, ny로 다음 칸을 visit 체크하기 전에

이미 그 칸이 visit 체크가 되어있으면, return 하도록 코드를 짰다.

 

 

이것도 조심해야 하는게, 경계체크 하는 부분에서 visit 체크를 같이 해버리면

사각형이 그려질 수 없어서 절대 답이 나오지 않는다.

(왜냐하면 사각형이 잘 그려졌다는건 첫점 == 끝점이라는건데, 끝점일 수도 있는데 retrun 해버리니까)

 

 

그래서 꼭

1. 경계체크 먼저 하고

2. 시작점 == 도착점인지 체크 하고

3. 그 다음에 visit 체크를 한 후

4. 다음 칸으로 이동하게 해야 한다.

 

 

팁

5번째 선거구 인구 합을 구하는게 약간 귀찮았는데,

생각해보니 1-4번 선거구 합은 쉽게 구할 수 있기 때문에

처음 입력받을때 전체 인구의 합을 구해준 뒤, 거기에서 1-4번째 선거구 인구의 합을 빼주면

5번째 선거구의 인구 합도 쉽게 구할 수 있다.

(코드에서 주석친 부분이 원래 코드)

 

이렇게 고치고 제출했더니 시간이 반 이상이나 줄어들었다.

 

 

코드

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

public class Main {
	
	private static int sx, sy, N, map[][], min = Integer.MAX_VALUE, totalSum = 0;
	private static int[] dx = {1, 1, -1, -1}, dy = {-1, 1, 1, -1};
	private static boolean[][] visit;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				totalSum += map[i][j];
			}
		}
		findStart();
		System.out.println(min);
	}

	private static void findStart() {
		for (int i = 0; i <= N - 3; i++) {
			for (int j = 1; j <= N - 2; j++) {
				visit[i][j] = true;
				sx = i; sy = j;
				backTracking(i, j, 0, 0, 0);
				visit[i][j] = false;
			}
		}
	}

	private static void backTracking(int x, int y, int d, int d1, int d2) {
		if (d > 3) return;
		
		int nx = x + dx[d];
		int ny = y + dy[d];
		
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return;

		if (sx == nx && sy == ny) {
			countCheck(nx, ny, d1, d2);
			return;
		}

		if (visit[nx][ny]) return;
			
		if (d == 0) d1++;
		else if (d == 1) d2++;
		
		visit[nx][ny] = true;
		backTracking(nx, ny, d, d1, d2);
		backTracking(nx, ny, d + 1, d1, d2);
		visit[nx][ny] = false;
	}

	private static void countCheck(int x, int y, int d1, int d2) {
		int[] sum = new int[5];
		for (int i = 0; i < x + d1; i++) {	//1
			for (int j = 0; j <= y; j++) {
				if (visit[i][j]) break;
				sum[0] += map[i][j];
			}
		}
		
		for (int i = 0; i <= x + d2; i++) {	//2
			for (int j = N - 1; j > y; j--) {
				if (visit[i][j]) break;
				sum[1] += map[i][j];
			}
		}
		
		for (int i = x + d1; i < N; i++) {	//3
			for (int j = 0; j < y + d2 - d1; j++) {
				if (visit[i][j]) break;
				sum[2] += map[i][j];
			}
		}
		
		for (int i = x + d2 + 1; i < N; i++) {	//4
			for (int j = N - 1; j >= y + d2 - d1; j--) {
				if (visit[i][j]) break;
				sum[3] += map[i][j];
			}
		}
		
//		sum[4] = map[x][y] + map[x + d1 + d2][y + d2 - d1];
//		for (int i = x + 1; i < x + d1 + d2; i++) {	//5
//			boolean flag = false;
//			for (int j = 0; j < N; j++) {
//				
//				if (!flag) {
//					if (visit[i][j]) {
//						flag = true;
//						sum[4] += map[i][j];
//					} 
//				} else {
//					sum[4] += map[i][j];
//					if (visit[i][j])
//						break;
//				}
//			}
//		}
		sum[4] = totalSum - sum[0] - sum[1] - sum[2] - sum[3];
		
		Arrays.sort(sum);
		int rslt = sum[4] - sum[0];
		if (min > rslt) min = rslt;
	}
}

위의 코드가 팁을 활용해서 푼 코드이다.

풀 때는 진짜 힘들었는데, 풀고 나니 배울 게 많은 문제였다는 생각이 들었다.

 

끝!