백준 [17779] 게리맨더링2

문제 출처 : https://www.acmicpc.net/problem/17779

 

삼성 역량테스트 2019년 하반기 기출문제이다.

 

푸는 방법은 여러가지가 있으며 대부분 그냥 for문을 사용하여 문제에 맞게 구현하였다.

 

범위에서 실수하지 말고 4중 for문으로 모든 경우에 문제에서 주어진 '구간 5' 부분을 채우고 나머지 부분을 채우는 구현문제이다.

 

필자는 '구간 5'부분을 채운다음 나머지 부분을 BFS탐색으로 채워 넣었는데 여기서 기본적인 for문의 구현방식보다 실행시간이 오래 걸렸다.

 

그리고 이 문제에서는 '구간 5'를 시작하는데 해당 모양이 이루어질 수 없는 상태라면 배제해도 된다. 그러니까 시작할 위치 (r,c)에 대해 d1,d2 값을 빼거나 더했을때, 범위를 벗어나는 경우는 무시하면 된다. 구현을 하다 '구간 5'를 채우는데 조금 시간이 걸렸다

 

풀이는

0) Map의 범위를 넘어가면 무시한다. 그게 아니면 아래를 시행한다.

1) (r,c)를 기준으로 먼저 '구간 5'의 경계선들을 Map에 5로 체크한다.

2) Map에 5로 채워진 경계선 내부를 다 5로 만들어준다.  

3) (0,0)을 기준으로 BFS를 시작한다. BFS는 모든 방문하지 않은 위치를 탐색하는데 해당 위치가 문제에서 주어진 조건에 따라 1,2,3,4 구간이면 그 위치에 각 값을 채워준다. 값이 이미 5라면 큐에 삽입만 하고 넘어간다.

4) 가장 큰 구간의 인구수와 작은 인구수의 차이를 구한다. 필자는 배열을 사용해 정렬하여 가장 큰 값과 작은값을 구하였다.

5) ans변수에 모든 경우에대해 가장 작은값을 계속 갱신하여 답을 구한다.

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
 
using namespace std;
 
int n, arr[110][110], dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 },ans=987654321;
 
void bfs(int r, int c, int d1, int d2) {
 
    queue<pair<int, int>>q;
    int visit[110][110] = { 0 }, num[5] = { 0 }, Map[110][110] = { 0 };
    int kx, ky;
    Map[r][c] = 5;
    if (r + d1 + d2 > n || c - d1 < 0 || c + d2 > n) return;
    for (int i = r, j = c; i <= r + d1; i++, j--) Map[i][j] = 5;
    for (int i = r, j = c; i <= r + d2; i++, j++) Map[i][j] = 5;
    for (int i = r + d1, j = c - d1; i <= r + d1 + d2; i++, j++) Map[i][j] = 5;
    for (int i = r + d2, j = c + d2; i <= r + d2 + d1; i++, j--) Map[i][j] = 5;
    for (int i = 0; i < n; i++) {
        int s, e,chk=0;
        for (int j = 0; j < n; j++) {
            if (Map[i][j] == 5 && chk == 0) {
                chk = 1;
                s = j;
            }
            else if (Map[i][j] == 5 && chk == 1) {
                chk = 2;
                e = j;
            }
        }
        if (chk != 2) continue;
        for (int j = s; j < e; j++) Map[i][j] = 5;
    }
    
    q.push({ 0,0 });
    visit[0][0] = 1;
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        if (x >= 0 && x < r + d1 && y >= 0 && y <= c && Map[x][y] != 5) Map[x][y] = 1;
        else if (x >= 0 && x <= r + d2 && y > c && y < n && Map[x][y] != 5) Map[x][y] = 2;
        else if (x >= r + d1 && x < n && y >= 0 && y < c - d1 + d2 && Map[x][y] != 5) Map[x][y] = 3;
        else if (x > r + d2 && x < n && y >= c - d1 + d2 && y < n && Map[x][y] != 5) Map[x][y] = 4;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int kx = x + dx[i];
            int ky = y + dy[i];
            if (kx < 0 || kx > n || ky < 0 || ky > n || visit[kx][ky] == 1) continue;
            visit[kx][ky] = 1;
            q.push({ kx,ky });
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (Map[i][j] == 1) num[0] = num[0] + arr[i][j];
            else if (Map[i][j] == 2) num[1] = num[1] + arr[i][j];
            else if (Map[i][j] == 3) num[2] = num[2] + arr[i][j];
            else if (Map[i][j] == 4) num[3] = num[3] + arr[i][j];
            else if (Map[i][j] == 5) num[4] = num[4] + arr[i][j];
        }
    }
    sort(num, num + 5);
    ans = min(ans, num[4] - num[0]);
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    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++) {
                    bfs(i, j, a, b);
                }
            }
        }
    }
    cout << ans;
    return 0;
}