[삼성SW테스트] 백준 17779번 - 게리맨더링 2 (정답률 58%)

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

17779번: 게리맨더링 2

2019년 상반기 삼성 SW테스트 기출 문제다. (유형: 시뮬레이션 + BFS)

 

처음에 이 문제를 접하고 꽤 복잡한 조건이 있다고 생각했는데 좀 고민해보니 기준점의 범위와 d1, d2의 범위를 4중루프를 돌며 가능한 경우인지 먼저 검사하고, 순차적으로

1. 5의 테두리를 그리고

2. 1과 2, 3, 4의 경계선을 그어준 뒤,

3. 1, 2, 3, 4의 시작점을 각각 (1, 1), (1, N), (N, 1), (N, N)으로 잡아주어 BFS탐색으로 각 숫자로 초기화 해주고

4. 마지막으로 5의 면적을 초기화 해준뒤

5. 최종적으로 각 선거구의 넓이를 구해 최대 선거구와 최소 선거구의 차이가 최소가 되는 경우를 구하면 된다.

 

처음에 접하면 당황할 수 있는 문제지만 진득하게 조건을 꼼꼼히 따지고 정확하게 구현하면 1시간 내외로 풀 수 있는 문제같다.

 

아래는 소스코드 (76ms / 1s)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
#define maxN 21
using namespace std;
typedef pair<int, int> pii;
vector<vector<pair<int, int> > > map, temp_map;
int N;
int answer = INF;
bool check[21][21];
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            map[i][j] = temp_map[i][j];
            check[i][j] = false;
        }
    }
}
 
bool possible(pii a, pii b, pii c, pii d){
    if (a.first < 1 || a.first > N || a.second < 1 || a.second > N ||
        b.first < 1 || b.first > N || b.second < 1 || b.second > N ||
        c.first < 1 || c.first > N || c.second < 1 || c.second > N ||
        d.first < 1 || d.first > N || d.second < 1 || d.second > N)
        return false;
    return true;
}
 
 
void make_1(){
    pii first_1 = make_pair(1, 1);
    queue<pii> q;
    q.push(first_1);
    check[1][1] = true;
    map[first_1.first][first_1.second].second = 1;
    while (!q.empty()){
        int front_x = q.front().first;
        int front_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            int nr = front_x + direction[i].dr;
            int nc = front_y + direction[i].dc;
            if (nr >= 1 && nr <= N && nc >= 1 && nc <= N){
                if (!check[nr][nc] && map[nr][nc].second == 0){
                    check[nr][nc] = true;
                    map[nr][nc].second = 1;
                    q.push(make_pair(nr, nc));
                }
            }
        }
    }
}
 
void make_2(){
    pii first_2 = make_pair(1, N);
    queue<pii> q;
    q.push(first_2);
    check[1][N] = true;
    map[first_2.first][first_2.second].second = 2;
    while (!q.empty()){
        int front_x = q.front().first;
        int front_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            int nr = front_x + direction[i].dr;
            int nc = front_y + direction[i].dc;
            if (nr >= 1 && nr <= N && nc >= 1 && nc <= N){
                if (!check[nr][nc] && map[nr][nc].second == 0){
                    check[nr][nc] = true;
                    map[nr][nc].second = 2;
                    q.push(make_pair(nr, nc));
                }
            }
        }
    }
}
 
void make_3(){
    pii first_3 = make_pair(N, 1);
    queue<pii> q;
    q.push(first_3);
    check[N][1] = true;
    map[first_3.first][first_3.second].second = 3;
    while (!q.empty()){
        int front_x = q.front().first;
        int front_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            int nr = front_x + direction[i].dr;
            int nc = front_y + direction[i].dc;
            if (nr >= 1 && nr <= N && nc >= 1 && nc <= N){
                if (!check[nr][nc] && map[nr][nc].second == 0){
                    check[nr][nc] = true;
                    map[nr][nc].second = 3;
                    q.push(make_pair(nr, nc));
                }
            }
        }
    }
}
 
void make_4(){
    pii first_4 = make_pair(N, N);
    queue<pii> q;
    q.push(first_4);
    check[N][N] = true;
    map[first_4.first][first_4.second].second = 4;
    while (!q.empty()){
        int front_x = q.front().first;
        int front_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            int nr = front_x + direction[i].dr;
            int nc = front_y + direction[i].dc;
            if (nr >= 1 && nr <= N && nc >= 1 && nc <= N){
                if (!check[nr][nc] && map[nr][nc].second == 0){
                    check[nr][nc] = true;
                    map[nr][nc].second = 4;
                    q.push(make_pair(nr, nc));
                }
            }
        }
    }
}
 
void make(pii left, pii right, pii std_point, pii bottom){
    // 선 그어주고 체크.
    for (int r = 1; r < std_point.first; r++){
        map[r][std_point.second].second = 1;
        check[r][std_point.second] = true;
    }
    for (int c = 1; c <= left.second; c++){
        map[left.first - 1][c].second = 1;
        check[left.first - 1][c] = true;
    }
    for (int r = 1; r <= std_point.first; r++){
        map[r][std_point.second + 1].second = 2;
        check[r][std_point.second + 1] = true;
    }
    for (int c = right.second + 1; c <= N; c++){
        map[right.first][c].second = 2;
        check[right.first][c] = true;
    }
    for (int c = left.second - 1; c >= 1; c--){
        map[left.first][c].second = 3;
        check[left.first][c] = true;
    }
    for (int r = bottom.first; r <= N; r++){
        map[r][bottom.second - 1].second = 3;
        check[r][bottom.second - 1] = true;
    }
    for (int r = bottom.first + 1; r <= N; r++){
        map[r][bottom.second].second = 4;
        check[r][bottom.second] = true;
    }
    for (int c = right.second; c <= N; c++){
        map[right.first + 1][c].second = 4;
        check[right.first + 1][c] = true;
    }
 
 
    // 5외곽선, 각 꼭지점 초기화 (1, 2, 3, 4), 구분선.
    map[left.first][left.second].second = 5;
    map[right.first][right.second].second = 5;
    map[std_point.first][std_point.second].second = 5;
    map[bottom.first][bottom.second].second = 5;
 
    for (int move = 1; move <= left.first - std_point.first; move++){
        map[left.first - move][left.second + move].second = 5;
        //check[left.first - move][left.second + move] = true;
    }
    for (int move = 1; move <= right.first - std_point.first; move++){
        map[std_point.first + move][std_point.second + move].second = 5;
        //check[std_point.first + move][std_point.second + move] = true;
    }
    for (int move = 1; move <= right.second - bottom.second; move++){
        map[right.first + move][right.second - move].second = 5;
        //check[right.first + move][right.second - move] = true;
    }
    for (int move = 1; move <= bottom.first - left.first; move++){
        map[bottom.first - move][bottom.second - move].second = 5;
        //check[bottom.first - move][bottom.second - move] = true;
    }
    //check[left.first][left.second] = false;
    //check[right.first][right.second] = false;
    //check[std_point.first][std_point.second] = false;
    //check[bottom.first][bottom.second] = false;
 
    make_1();
    make_2();
    make_3();
    make_4();
 
    pii start_5 = make_pair(std_point.first + 1, std_point.second);
    queue<pii> q;
    q.push(start_5);
    map[start_5.first][start_5.second].second = 5;
    check[start_5.first][start_5.second] = true;
    while (!q.empty()){
        int front_x = q.front().first;
        int front_y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++){
            int nx = front_x + direction[i].dr;
            int ny = front_y + direction[i].dc;
            if (nx >= 1 && ny <= N && ny >= 1 && nx <= N){
                if ((!check[nx][ny] && map[nx][ny].second == 0) || 
                    (!check[nx][ny] && map[nx][ny].second == 5)){
                    check[nx][ny] = true;
                    map[nx][ny].second = 5;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }
    // 5 채우기 완료.
 
    
    // 각 숫자 경계선 완료.
}
 
 
void calculation(){
    int Sum[5] = { 0, 0, 0, 0, 0 };
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            int cur_category = map[i][j].second;
            Sum[cur_category-1] += map[i][j].first;
        }
    }
    int maximum = -1; int minimum = INF;
    for (int i = 0; i < 5; i++){
        maximum = max(maximum, Sum[i]);
        minimum = min(minimum, Sum[i]);
    }
    answer = min(answer, abs(maximum - minimum));
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    map.assign(N + 1, vector<pair<int, int> >(N + 1, make_pair(0, 0)));
    temp_map.assign(N + 1, vector<pair<int, int> >(N + 1, make_pair(0, 0)));
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            int a;
            cin >> a;
            map[i][j].first = a;
            map[i][j].second = 0;
            temp_map[i][j].first = a;
            temp_map[i][j].second = 0;
        }
    }
    reset();
 
    for (int x = 1; x <= N - 2; x++){
        for (int y = 2; y <= N - 1; y++){
            for (int d1 = 1; d1 <= maxN; d1++){
                for (int d2 = 1; d2 <= maxN; d2++){
                    pii std_point = make_pair(x, y);
                    pii left = make_pair(x + d1, y - d1);
                    pii right = make_pair(x + d2, y + d2);
                    pii bottom = make_pair(x + d1 + d2, y + d2 - d1);
                    if (possible(std_point, left, right, bottom)){
                        make(left, right, std_point, bottom);
                        /*
                        cout << '\n';
                        cout << "x: " << x << " y: " << y << " d1: " << d1 << " d2: " << d2 << '\n';
                        cout << '\n';
                        for (int i = 1; i <= N; i++){
                            for (int j = 1; j <= N; j++){
                                cout << map[i][j].second << " ";
                            }
                            cout << '\n';
                        }
                        cout << '\n';
                        */
                        calculation();
                        reset();
                        // 내부 점 하나 잡아서 bfs 탐색.
                    }                    
                }
            }
        }
    }
    cout << answer << '\n';
    return 0;
}