BOJ 17779. 게리맨더링 2
문제 설명
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
선거구를 나누는 방법은 다음과 같다.
-
기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (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) -
경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
-
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
아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.
|
|
|
| x = 2, y = 4, d1 = 2, d2 = 2 | x = 2, y = 5, d1 = 3, d2 = 2 | x = 4, y = 3, d1 = 1, d2 = 1 |
구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.
입력
첫째 줄에 재현시의 크기 N이 주어진다.
둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.
출력
첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.
제한
5 ≤ N ≤ 20
1 ≤ A[r][c] ≤ 100
[입력]
6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9[출력]
18[입력]
6
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5[출력]
20[입력]
8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6[출력]
23
|
|
|
| 예제 입력 1 | 예제 입력 2 | 예제 입력 3 |
1. 문제 해석
1.1. 문제 유형 분석
삼성전자 기출문제 중에서는 이차원 배열 상에서 시뮬레이션 하는 문제가 많이 출제된다. 최근에 출제된 문제들을 보면 단순히 완전 탐색하여 2~3중 for문에서 끝나는 문제는 거의 없다. 하지만 7~8중 for문까지 가는 경우가 많다. 하지만 크게 나누어 보면 3~4중 for문 + DFS or BFS 와 같은 형태로 섞어서 풀이해야 하는 경우이다.
N중 for문으로 올라가게 될때는 단순히 모든 과정을 한번에 머리로 이해하기는 매우 어렵다. 따라서 큰 덩어리로 나누어서 생각하는 것이 중요하다. 큰 문제에서 작은 문제로, Top-down 방식으로 함수를 구성한다면 생각이 훨씬 수월하다. 이 문제의 경우, 1) 선거구를 나눈다. 2) 각 선거구를 채운다. 3) 인구 수 차이의 최솟값을 구한다. 이런식으로 나눌 수 있다. 그러면 정확히는 모르겠지만 각 선거구를 나누는 함수를 구현하고, 각 선거구를 채우는 함수를 구현하고, 인구 수 차이의 최솟값을 구하면 정답을 구할 수 있다.
실제로 시험장에서는 이 문제처럼 인덱스가 무엇인지 지정할 수 있게 변수가 주어지지 않았던 것 같다. 따라서 문제의 조건을 상세히 분석하여 어떠한 변수를 인덱스로 하여 반복할 것인지, 이차원 배열 상에서 무슨 점을 어디까지 반복시킬 수 있는지 파악하는 것이 중요하다. 이 문제도 테트로미노 처럼 마름모 모양의 각 꼭짓점을 이동시켜가면서 반복하는 것이 기본이 된다.
1.2. 문제 풀이 설계
이 문제는 선거구를 나누는 과정이 그대로 주어졌기 때문에 그대로 따라주면 된다. 단, 경계선의 조건을 잘 따져보아야 한다.
-
기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (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)
-
경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
-
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
|
|
|
| 5번 선거구 경계선을 그린다 | 꼭짓점을 기준으로 각 선거구의 경계선을 그린다 | 각 선거구를 해당 선거구 번호로 마킹한다 |
각 꼭짓점을 기준으로 경계선을 먼저 그리고, 색칠한다. 색칠할 때는 BFS나 DFS, 혹은 브루트 포스로도 가능하지만 DFS가 가장 깔끔하다. 각 꼭짓점을 기준으로 반복을 수행하므로 각 꼭짓점의 범위를 정확히 확인해야 한다. 범위를 벗어나지 않으면서 완전탐색을 수행할 수 있다.
|
|
|
| 5번 선거구가 최소일 때 각 꼭짓점 | 1 ≤ x ≤ N-2, 0 ≤ y ≤ N-3 0 ≤ x+d1 ≤ N-3, 1 ≤ y-d1 ≤ N-2 |
2 ≤ x+d2 ≤ N-1, 1 ≤ y+d2 ≤ N-2 1 ≤ x+d1+d2 ≤ N-2, 2 ≤ y+d1+d2 ≤ N-1 |
2. 문제 풀이
2.1. DFS로 구현
#include <iostream>
#include <cstring> // memset
using namespace std;
#define INF 987654321
int N;
int map[20][20];
int group[20][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
void DFS(int r, int c, int value){
if(r < 0 || r > N-1 || c < 0 || c > N-1) return; // 범위를 넘어서면 종료
if(group[r][c]!=0) return; // 값이 없으면 종료
group[r][c] = value; // 값을 채움
for(int i=0; i<4; ++i)
DFS(r+dx[i],c+dy[i], value);
}
int divide(int x, int y, int d1, int d2){
for(int i = 0; i <= d1; ++i){
group[x+i][y-i] = 5;
group[x+d2+i][y+d2-i] = 5;
}
for(int i = 0; i <= d2; ++i){
group[x+i][y+i] = 5;
group[x+d1+i][y-d1+i] = 5;
}
for(int r = x-1; r >= 0; --r) // 선거구 1번 경계선
group[r][y] = 1;
for(int c = y+d2+1; c < N; ++c) // 선거구 2번 경계선
group[x+d2][c] = 2;
for(int c = y-d1-1; c >= 0; --c) // 선거구 3번 경계선
group[x+d1][c] = 3;
for(int r = x+d1+d2+1; r < N; ++r) // 선거구 4번 경계선
group[r][y-d1+d2] = 4;
DFS(0,0,1); // 1번 선거구 색칠
DFS(0,N-1,2); // 2번 선거구 색칠
DFS(N-1,0,3); // 3번 선거구 색칠
DFS(N-1,N-1,4); // 4번 선거구 색칠
int people[6] ={0};
for(int r = 0; r < N; ++r) // 각 선거구에 해당하는 인구를 더함
for(int c = 0; c < N; ++c)
people[group[r][c]] += map[r][c];
people[5] += people[0]; // 0번 선거구값을 5번 선거구에 더함
int minP = INF;
int maxP = -INF;
for(int i=1; i<=5; ++i){
minP = min(minP, people[i]);
maxP = max(maxP, people[i]);
}
return maxP - minP;
}
int solve(){
int ret = INF;
for(int x=0; x <= N-3; x++){
for(int y=1; y<= N-2; ++y){
for(int d1=1; d1 <= N-1 && y-d1 >= 0; ++d1){
for(int d2=1; x+d1+d2 <= N-1 && y-d1+d2 <= N-1; ++d2){
memset(group, 0, sizeof(group));
ret = min(ret, divide(x, y, d1, d2));
}
}
}
}
return ret;
}
int main(){
cin >> N;
for(int i=0; i<N; ++i)
for(int j=0; j<N; ++j)
cin >> map[i][j];
cout << solve() << endl;
return 0;
}2.2. BFS로 구현
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define INF 987654321
int N;
int map[20][20];
int group[20][20];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
void BFS(int r, int c, int value){
queue<pair<int, int> > q;
q.push(make_pair(r,c));
group[r][c] = value;
while(!q.empty()){
r = q.front().first;
c = q.front().second;
q.pop();
for(int i=0; i<4; ++i){
int nr = r+dx[i];
int nc = c+dy[i];
if(nr >= 0 && nr < N && nc >= 0 && nc < N){
if(group[nr][nc]==0) {
group[nr][nc] = value;
q.push(make_pair(nr,nc));
}
}
}
}
}
int divide(int x, int y, int d1, int d2){
...
BFS(0,0,1); // 1번 선거구 색칠
BFS(0,N-1,2); // 2번 선거구 색칠
BFS(N-1,0,3); // 3번 선거구 색칠
BFS(N-1,N-1,4); // 4번 선거구 색칠
...
int solve(){
...
}
int main(){
...
}