백준 17779 - 게리맨더링2

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

17779번: 게리맨더링 2

문제 설명

---

 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다.

구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

 

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다.

(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

2. 다음 칸은 경계선이다.

- (x, y), (x+1, y-1), ..., (x+d1, y-d1)

- (x, y), (x+1, y+1), ..., (x+d2, y+d2)

- (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)

- (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.

4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.

- 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y

- 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N

- 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2

- 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

 

 

접근 방법

---

프로그램상의 x, y의 좌표계 방향의 변경과 방정식을 통한 영역을 나누는 것이 많이 까다롭고 힘들었지만 이 부분을 제외한 부분은 쉽게 구현할 수 있을 것입니다.

방정식을 위한 좌표와 기울기 

 1. r-x = -1(c-y)   >>   r>=x-(c-y)  

 2. r-x = 1(c-y)   >>   r>=x+(c-y)  

 3. r-x-d1 = (c-y+d1)   >>   c= y-d1+(r-x-d1)  

 4. r-x-d2 = -(c-y-d2)   >>   c=y+d2+x-r+d2  

 (그림에서 3번과 4번이 바뀌어져 있습니다..) 

단 x,y는 상수로 정해져 있으며 x는 y좌표를 의미하고 y는 x좌표를 의미한다. 주의할것!!!

다음으로 각 구역의 y좌표와 x좌표는 (r,c) 이다.

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int map[21][21];
int area[21][21];
int ans,n;
bool visited[21][21];
int dx[]= {0,1,0,-1};
int dy[]= {1,0,-1,0};
const int INF = 987654321;

int five_area(int x,int y,int d1,int d2){
	vector<int> people(5, 0);
	memset(area,0,sizeof(area));
	memset(visited,false,sizeof(visited));
	//(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
	// 1) (x, y), (x+1, y-1), ..., (x+d1, y-d1)
	// 2) (x, y), (x+1, y+1), ..., (x+d2, y+d2)
	// 3) (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
	// 4) (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

	// 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
	// 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
	// 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
	// 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
	for(int r=1;r<=n;r++){
		for(int c=1;c<=n;c++){
			//r-x = -1(c-y) >> r>=x-(c-y); r>=x;
			if(r<x+d1 && c<=y &&!(c>=y-(r-x))){
				people[0] += map[r][c];
			}//r-x = 1(c-y) >> r>=x+(c-y); r>=x;
			else if(r<=x+d2 && c>y && !(c<=y+(r-x))){
				people[1] += map[r][c];
			}
			//r-x-d1 = (c-y+d1) >> c= y-d1+(r-x-d1)
			else if(r>=x+d1 && c<y-d1+d2 && !(c>=(y-d1-x-d1+r))){
				people[2] += map[r][c];
			}
			//r-x-d2 = -(c-y-d2) >> c=y+d2+x-r+d2
			else if(r>x+d2 && c>=y-d1+d2 && !(c<=(y+d2+x+d2-r))){
				people[3] += map[r][c];	
			}
			else{
				people[4] += map[r][c];
			}
		}
	}
	sort(people.begin(), people.end());
	return people[4] - people[0];
}
int devide_area(){
	int x,y,d1,d2;
	int ans = INF;
	for(int x=1;x<=n-2;x++){
		for(int y=2;y<=n-1;y++){
			for(int d1=1;d1 <=y-1 && d1<=n-x-1;d1++){
				for(int d2=1; d2<=n-y && d2<=n-x-1;d2++){
					ans = min(five_area(x,y,d1,d2),ans);
				}
			}
		}
	}
	return ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>map[i][j];
        }
	}
    cout<<devide_area();
    return 0;
}

funny algorithm ^0^