17779번: 게리맨더링 2
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름
www.acmicpc.net
1. 풀이방법
- 구현문제입니다.
- 나머지 선거구는 문제에서 이미 범위가 다 주어져서 쉬운 문제입니다.
- 문제는 5번선거구를 처리하는 것입니다.
- 저는 가장자리를 먼저 구해서 맵에 체크 해놓고, (x+1,y) 좌표를 기준으로 bfs를 돌린 뒤, 4면이 다 5선거구로 둘러쌓여 있는 지역을 5번 선거구에 포함하여 주었습니다.
- 0 5 0 0 0
5 0 5 0 0
0 5 0 5 0
0 0 5 0 0
- 위와 같은 예시는 4방향탐색 bfs로는 5선거구에 포함시킬 수 없기 때문입니다.
2. 주의사항
- 문제조건에 왠만하면 범위를 맞추자.... (0~n-1)로 고집하지말고... 1~n으로 맞춰서 하자....
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
pair<int, int> ground[22][22]; //first =선거구, second= 구역별 인원
int n;
queue<pair<int, int>> tmpq;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int numcount[6];
int resultmin = 20000;
void inputs() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> ground[i][j].second;
}
}
}
bool boundcheck(int i, int j, int a, int b) {
return ((i + a + b) <= n && (j - a >= 1) && (j + b <= n));
}
void initground() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ground[i][j].first = 0;
}
}
}
bool bfsboundcheck(int x, int y) {
return (x <= n&& x >= 1 && y >= 1 && y <= n);
}
void bfs(int x, int y) {
ground[x][y].first = 5;
tmpq.push({ x,y });
while (!tmpq.empty()) {
int qsize = tmpq.size();
while (qsize--) {
int nextx = tmpq.front().first;
int nexty = tmpq.front().second;
tmpq.pop();
for (int i = 0; i < 4; i++) {
int tx = nextx + dx[i];
int ty = nexty + dy[i];
if (bfsboundcheck(tx, ty) && ground[tx][ty].first != 5) {
tmpq.push({ tx,ty });
ground[tx][ty].first = 5;
}
}
}
}
}
void makeoutside(int x,int y,int d1,int d2) {
// 일단 경계선
for (int i = 0; i <= d1; i++) {
ground[x + i][y - i].first = 5;
ground[x + d2 + i][y + d2 - i].first = 5;
}
for (int j = 0; j <= d2; j++) {
ground[x + j][y + j].first = 5;
ground[x + d1 + j][y - d1 + j].first = 5;
}
//bfs 돌리고 + 4면이 모두 5인 곳은 따로 체크
if (ground[x + 1][y].first == 0) bfs(x + 1, y);
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int tmpcount = 0;
for (int k = 0; k < 4; k++) {
if (ground[i + dx[k]][j + dy[k]].first == 5) {
tmpcount++;
}
else break;
}
if (ground[i][j].first != 5 && tmpcount == 4) { ground[i][j].first = 5; }
}
}
for (int i = 1; i < x + d1; i++) { //1번 선거구
for (int j = 1; j <= y; j++) {
if (ground[i][j].first == 5) continue;
ground[i][j].first = 1;
}
}
for (int i = 1; i <= x + d2; i++) { //2번 선거구
for (int j = y+1; j <= n; j++) {
if (ground[i][j].first == 5) continue;
ground[i][j].first = 2;
}
}
for (int i = x + d1; i <= n; i++) { //3번 선거구
for (int j = 1; j < y - d1 + d2;j++) {
if (ground[i][j].first == 5) continue;
ground[i][j].first = 3;
}
}
for (int i = x + d2+1; i <= n; i++) {
for (int j = y - d1 + d2; j <= n; j++) {
if (ground[i][j].first == 5) continue;
ground[i][j].first = 4;
}
}
}
void numcheckreset() {
for (int i = 1; i <= 5; i++) {
numcount[i] = 0;
}
}
void getnumcount() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
numcount[ground[i][j].first] += ground[i][j].second;
}
}
}
bool emptycheck() {
for (int i = 1; i <= 5; i++) {
if (numcount[i] == 0) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (boundcheck(i, j, a, b)) { //범위를 만족할 때만
initground();
makeoutside(i,j,a,b);
numcheckreset();
getnumcount();
if (emptycheck()) continue; //적어도 하나의 구역 포함
sort(numcount + 1, numcount + 6);
resultmin = min(resultmin, numcount[5] - numcount[1]);
}
}
}
}
}
cout << resultmin;
return 0;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 17837 [C++] (0) | 2021.03.06 |
|---|---|
| 백준 16235 [C++] (0) | 2021.03.06 |
| 백준 19237 [C++] (0) | 2021.03.05 |
| 백준 17140 [C++] (0) | 2021.01.24 |
| 백준 2726 [C++] (0) | 2021.01.16 |