17779 게리맨더링2 : https://www.acmicpc.net/problem/17779
Problem
Solve
문제가 꽤나 복잡해보여서 겁부터 먹었지만, 풀다보니 문제에서 조건을 다 제공해주고있었다.
특정 기준점을 선택하고 경계선을 그어보게 되면 평행사변형의 모양이 된다.
그리고 경계선 바깥쪽으로 4개의 선거구가 형성되고 경계선을 포함한 안쪽이 5번 선거구가 된다.
처음에는 선거구 구역(r,c) 조건의 시작부분부터 구역을 정하느라 BFS를 사용했는데, 생각해보니 굳이 그렇게 할 필요가 없었다. 경계선 바깥쪽에서 경계선 쪽으로 각 선거구의 범위를 탐색하면서 경계선과 그 안쪽을 탐색하지 않고 다른 부분만 탐색할수 있었고 각 구역을 1번 선거구:1, 2번 선거구:2, 3번 선거구:3, 4번 선거구:4, 5번 선거구:0으로 표시한다.
각 구역을 나누었다면 구역의 번호의 개수를 구하고 구역 최대 개수와 최소 개수를 정렬을 통해 구한 후 두개의 값 차이의 최소값이 모든 경우의 수의 최소값으로 갱신되도록 반복한다.
기준 좌표 와 d1,d2 구하는 함수 O(N^2 N^2), 경계선 긋는 함수 O(N), 구역 구하는 함수 O((N^2)4) (d1,d2는 반비례하므로 대강 최대 N으로 놓으면)으로 해도 O(N^6)은 되지만 N이 20이므로 충분히 가능하다.
Code
package org.algorithm.java.hyunjong.Algorithm.BOJ.삼성기출;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class 게리맨더링2 {
static int N;
static int[][] map;
static boolean[][] lineMap;
static int[][] rangeMap;
static int[] dy = {-1, 0, 1, 0};
static int[] dx = {0, -1, 0, 1};
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
answer = Integer.MAX_VALUE;
//기준좌표와 경계선 생성 함수
setPointAndLine();
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
static void countUserNumber() {
int selector1 = 0;
int selector2 = 0;
int selector3 = 0;
int selector4 = 0;
int selector5 = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int selector = rangeMap[i][j];
if (selector == 1) {
selector1 += map[i][j];
} else if (selector == 2) {
selector2 += map[i][j];
} else if (selector == 3) {
selector3 += map[i][j];
} else if (selector == 4) {
selector4 += map[i][j];
} else {
selector5 += map[i][j];
}
}
}
//각 구역의 인원 수 배열에 저장 후 정렬하게 되면 0은 최소값, 4는 최대값이 된다.
int[] selectors = new int[] {selector1, selector2, selector3, selector4, selector5};
Arrays.sort(selectors);
int max = selectors[4];
int min = selectors[0];
answer = Math.min(answer, max - min);
}
static void setRange(int x, int y, int d1, int d2) {
//구역 배열
rangeMap = new int[N + 1][N + 1];
//각 구역은 경계선 바깥부분에서 경계선쪽으로 탐색하며 경계선을 만나면 다음 행 탐색
//1
for(int i=1;i<x+d1;i++){
for(int j=1;j<=y;j++){
if(lineMap[i][j]) break;
rangeMap[i][j] = 1;
}
}
//2
for(int i=1;i<=x+d2;i++){
for(int j=N;j>y;j--){
if(lineMap[i][j]) break;
rangeMap[i][j] = 2;
}
}
//3
for(int i=x+d1;i<=N;i++){
for(int j=1;j<y-d1+d2;j++){
if(lineMap[i][j]) break;
rangeMap[i][j] = 3;
}
}
//4
for(int i= x+d2+1;i<=N;i++){
for(int j=N;j>=y-d1+d2;j--){
if(lineMap[i][j]) break;
rangeMap[i][j] = 4;
}
}
}
static void setLine(int x, int y, int d1, int d2) {
//경계선 배열
lineMap = new boolean[N + 1][N + 1];
//1 & 4
for (int i = 0; i <= d1; i++) {
lineMap[x + i][y - i] = true;
lineMap[x + d2 + i][y + d2 - i] = true;
}
//2 & 3
for (int i = 0; i <= d2; i++) {
lineMap[x + i][y + i] = true;
lineMap[x + d1 + i][y - d1 + i] = true;
}
}
//BFS로 구역 구하는 함수
// static void setSelector1(int x, int y, int d1, int d2) {
// Queue<int[]> queue = new LinkedList<>();
// boolean[][] visit = new boolean[N + 1][N + 1];
// queue.add(new int[] {1, 1});
//
// while (!queue.isEmpty()) {
// int[] current = queue.poll();
//
// for (int i = 0; i < 4; i++) {
// int ny = current[0] + dy[i];
// int nx = current[1] + dx[i];
//
// if (ny >= 1 && ny < x + d1 && nx >= 1 && nx <= y && !visit[ny][nx] && !lineMap[ny][nx]) {
// visit[ny][nx] = true;
// queue.add(new int[] {ny, nx});
// rangeMap[ny][nx] = 1;
// }
// }
// }
// }
//
// static void setSelector2(int x, int y, int d1, int d2) {
// Queue<int[]> queue = new LinkedList<>();
// boolean[][] visit = new boolean[N + 1][N + 1];
// queue.add(new int[] {0, N});
//
// while (!queue.isEmpty()) {
// int[] current = queue.poll();
// for (int i = 0; i < 4; i++) {
// int ny = current[0] + dy[i];
// int nx = current[1] + dx[i];
// if (ny >= 1 && ny <= x + d2 && nx > y && nx <= N && !visit[ny][nx] && !lineMap[ny][nx]) {
// visit[ny][nx] = true;
// queue.add(new int[] {ny, nx});
// rangeMap[ny][nx] = 2;
// }
// }
// }
// }
//
// static void setSelector3(int x, int y, int d1, int d2) {
// Queue<int[]> queue = new LinkedList<>();
// boolean[][] visit = new boolean[N + 1][N + 1];
// queue.add(new int[] {N, 0});
//
// while (!queue.isEmpty()) {
// int[] current = queue.poll();
// for (int i = 0; i < 4; i++) {
// int ny = current[0] + dy[i];
// int nx = current[1] + dx[i];
// if (ny >= x + d1 && ny <= N && nx >= 1 && nx < y - d1 + d2 && !visit[ny][nx] && !lineMap[ny][nx]) {
// visit[ny][nx] = true;
// queue.add(new int[] {ny, nx});
// rangeMap[ny][nx] = 3;
// }
// }
// }
// }
//
// static void setSelector4(int x, int y, int d1, int d2) {
// Queue<int[]> queue = new LinkedList<>();
// boolean[][] visit = new boolean[N + 1][N + 1];
// queue.add(new int[] {N, N});
//
// while (!queue.isEmpty()) {
// int[] current = queue.poll();
// for (int i = 0; i < 4; i++) {
// int ny = current[0] + dy[i];
// int nx = current[1] + dx[i];
// if (ny > x + d2 && ny <= N && nx >= y - d1 + d2 && nx <= N && !visit[ny][nx] && !lineMap[ny][nx]) {
// visit[ny][nx] = true;
// queue.add(new int[] {ny, nx});
// rangeMap[ny][nx] = 4;
// }
// }
// }
// }
static void setPointAndLine() {
//기준 좌표
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
//d1
for (int d1 = 1; d1 <= N; d1++) {
if (y - d1 < 1)
break;
//d2
for (int d2 = 1; d2 <= N; d2++) {
if (x + d1 + d2 > N || y + d2 > N)
break;
//경계선 긋기
setLine(x, y, d1, d2);
//구역 정하기
setRange(x, y, d1, d2);
//각 구역 인원 및 최대 최소의 차이 구하기
countUserNumber();
}
}
}
}
}
}
Result
쫄보
Reference
내 꿈은 좋은 개발자