백준 17779 게리맨더링 2 - 삼성 SW 역량 테스트 기출

백준 17779 게리맨더링 2 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

17779번: 게리맨더링 2

 

2. 문제 해결에 대한 아이디어

1. 이 문제는 모든 경우의 수를 해보면 된다. (완전 탐색 / Brute Force)

   . 그렇기 때문에 y, x, d1, d2의 모든 경우를 따져봐야한다.

   . 여기서 수행 시간을 줄이려면 경우를 따지기 전에 d1과 d2가 가능한 값인지 체크해야한다. (코드 참고)

   . 사전 체크를 한 경우와 안 한 경우 사용 메모리는 5배 차이나고 시간은 약 200ms 차이 났다.

2. 문제에서는 행을 x로 열을 y로 했고 나는 행을 y로 열을 x로 했다. (괜히 그런거 같다.)

3. 1 <= d1, d2 < N 임을 확인할 수 있다.

   . N * N 격자에서 대각선의 칸 또한 N 칸이다

   . 기준점을 제외 했을 때, d1과 d2는 최대 N-1이다.

4. 게리맨더링은 아래의 순서로 진행한다. (int[][] union / 매번 초기화 필요)

   . 5번 구역 채우기

      . 문제의 조건에 따라 5번의 경계를 만든다.

      . BFS로 경계 안을 5번으로 채운다.

   . union에 조건에 따라 나머지 값을 채운다.

   . 모든 구역이 정해지면 각 구역별 인구를 합하여 int[] number에 넣는다. (index = 구역 번호)

   . sorting 하여 가장 많은 인구 수와 적은 인구 수의 차를 구한 후 gap과 비교한다.

5. 5번을 채우는 BFS는 아래와 같이 구현했다.

   . 기준점보다 한 행 위에 있는 칸에서 BFS를 시작한다.

   . 5를 만날 때까지, 아래 행으로 이동하며 5를 넣는다.

   . 이제 시작 지점을 처음 기준점 기준에서 왼쪽 아래 혹은 오른쪽 아래로 옮겨 위를 반복한다.

   . 단, 시작 지점은 서쪽 혹은 동쪽 꼭지점이 되면 안 된다. 

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static class Pair {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static int N;
	static int[][] board;
	static int[][] union; // 매번 초기화 시킬 것
	static int gap = 9999999;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br;
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\게리맨더링2_17779\\input.txt"));

		N = Integer.parseInt(br.readLine().split(" ")[0]);

		board = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
			}
		}

		union = new int[N][N];
		search();
		System.out.println(gap);
		br.close();
	}

	static void search() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int d1 = 1; d1 < N; d1++) {
					for (int d2 = 1; d2 < N; d2++) {
						if (i + d1 >= N || j - d1 < 0)
							continue;
						if (i + d2 >= N || j + d2 >= N)
							continue;

						make(i, j, d1, d2);
					}
				}
			}
		}

	}

	private static void make(int y, int x, int d1, int d2) {
		union = new int[N][N];
		union[y][x] = 5;
		// 복쪽에서 왼쪽 아래로
		int yy = y;
		int xx = x;
		for (int i = 0; i < d1; i++) {
			yy = yy + 1;
			xx = xx - 1;
			if (yy >= N || xx >= N || yy < 0 || xx < 0)
				return;
			union[yy][xx] = 5;
		}

		// 서쪽에서 오른쪽 아래로
		for (int i = 0; i < d2; i++) {
			yy = yy + 1;
			xx = xx + 1;
			if (yy >= N || xx >= N || yy < 0 || xx < 0)
				return;
			union[yy][xx] = 5;
		}

		// 남쪽에서 오른쪽 위로
		for (int i = 0; i < d1; i++) {
			yy = yy - 1;
			xx = xx + 1;
			if (yy >= N || xx >= N || yy < 0 || xx < 0)
				return;
			union[yy][xx] = 5;
		}

		// 동쪽에서 왼쪽 위로
		for (int i = 0; i < d2; i++) {
			yy = yy - 1;
			xx = xx - 1;
			if (yy >= N || xx >= N || yy < 0 || xx < 0)
				return;
			union[yy][xx] = 5;
		}

		yy = y;
		xx = x;
		for (int i = 0; i < d1; i++) {
			Queue<Pair> q = new LinkedList<>();
			q.add(new Pair(yy + 1, xx));
			union[yy + 1][xx] = 5;
			while (!q.isEmpty()) {
				Pair now = q.poll();
				int nowY = now.y;
				int nowX = now.x;
				union[nowY][nowX] = 5;

				int nextY = nowY + 1;
				int nextX = nowX;
				if (union[nextY][nextX] == 5)
					break;
				q.add(new Pair(nextY, nextX));

			}
			yy = yy + 1;
			xx = xx - 1;
		}

		yy = y;
		xx = x;
		for (int i = 0; i < d2; i++) {
			Queue<Pair> q = new LinkedList<>();
			q.add(new Pair(yy + 1, xx));
			union[yy + 1][xx] = 5;
			while (!q.isEmpty()) {
				Pair now = q.poll();
				int nowY = now.y;
				int nowX = now.x;
				union[nowY][nowX] = 5;

				int nextY = nowY + 1;
				int nextX = nowX;
				if (union[nextY][nextX] == 5)
					break;
				q.add(new Pair(nextY, nextX));

			}
			yy = yy + 1;
			xx = xx + 1;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (union[i][j] != 0)
					continue;
				if (i >= 0 && i < y + d1 && j >= 0 && j <= x) {
					union[i][j] = 1;
				} else if (i >= 0 && i <= y + d2 && j > x && j <= N - 1) {
					union[i][j] = 2;
				} else if (i >= y + d1 && i <= N - 1 && j >= 0 && j < x - d1 + d2) {
					union[i][j] = 3;
				} else if (i > y + d2 && i <= N - 1 && j >= x - d1 + d2 && j <= N - 1) {
					union[i][j] = 4;
				} else {
					union[i][j] = 5;
				}
			}
		}
		int[] number = new int[6];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				number[union[i][j]] += board[i][j];
			}
		}

		Arrays.sort(number);
		int tempGap = number[5] - number[1];

		gap = Math.min(gap, tempGap);

	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 메모리 초과를 계속 받았었는데 5번을 채우는 BFS에 대한 조건을 잘못해서 발생했다. (아래로 가야하는데 위로 감;;)

2. 코드를 꼼꼼하게 짜도록 노력해야겠다.