Google Kick Start 2019 Round A _ problem B : Parcels(2)

새로운 해결 방향 : 사무실과의 거리가 k보다 더 큰 지역들을 대상으로 모든 거리가 k 이하인 지점에 새로운 사무실을 건설하는 방향입니다. 

만약, 이 k값이 주어진다면 만족하는 어떤 '0' 지점들과 사무실과의 거리가 k이상인 지점들과의 거리를 구해 모든 거리가 k-1이하면 그 지점이 '1'의 후보지가 되는 것이지요. 이것을 sub-problem이라 하겠습니다.

먼저, 주어진 map상태에서 bfs를 실행해 '0' 지점들의 사무실과의 최소 거리를 구합니다.

구해진 거리 정보는 큐에 쌓이게 되는데요, 나중에 '1'의 후보지를 탐색하기 위해 거리가 처음 큐에 저장되는 인덱스 정보를 따로 배열에 저장합니다. 

 

예제) 큐에 0 0 0 1 1 1 2 2 2 3 ... 이런 식으로 거리 정보가 쌓인 다면, 배열에 0,3,6,9..... 이런식으로 정보가 저장됩니다.

 

그 후, 어떤 거리 k에 대해서 sub-problem에 대한 답을 찾습니다. 

k의 범위는 1부터 가장 멀리 떨어진 거리가 되겠습니다. 

모든 범위를 탐색해야하기 때문에 '이진탐색'을 적용하면 효율을 높일 수 있겠죠?!

 

예제)

1	0(1)	0(2)
0(1)	0(2)	0(3)
0(2)	0(3)	0(4)

빨간 숫자는 사무실과의 거리를 나타냅니다.

이진탐색을 적용하기 떄문에 시작(1)+끝(4) / 2 값이 2부터 탐색합니다.

거리가 3 이상인 지점은 3개 있죠. 그 지점들과 '0'인 지점들의 거리를 구합니다.

모든 거리가 2 이하인 지점이 있다면 그 지점이 '1'의 후보지가 되는 것이고 '2'가 정답이 될 수 있는 것입니다.

그 후, 조건을 만족하는 지점이 있다면 k 왼쪽 부분 (시작(1)+k-1(1)) 을 탐색하고, 

없다면 k의 오른쪽 부분을(k+1(3),4) 탐색하면 됩니다.

여기선 조건을 만족하기 (2,2)지점이 조건을 만족하기 때문에 일단 정답은 2로 설정한 후왼쪽 부분을 탐색합니다.

k = 1일 때, 탐색해보시면 안되는 것을 알 수 있기 때문에 정답은 2가 되는 것이지요.

 

이런 식으로 방향을 잡고, 코드를 짜니 이전 글에서 소개한 완전탐색의 문제를 해결할 수 있었습니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
 
using namespace std;
 
int r, c;
 
int map[250][250]; // map 기본 정보
int distance_list[500]; // 거리정보 
int max_distance = 0; // 가장 긴 거리
 
int check[250][250];
 
int dir_x[4] = { 1,0,-1,0 };
int dir_y[4] = { 0,1,0,-1 };
 
int one_x[62500]; // 배달 시간 구하는 que
int one_y[62500];
int one_d[62500];
int one_top = 0;
int one_rear = 0;
 
int zero_x[62500];
int zero_y[62500];
int zero_num = 0;
 
int k = 0;
 
void bfs() {
    while (one_rear < one_top) {
        int x = one_x[one_rear];
        int y = one_y[one_rear];
        int d = one_d[one_rear++];
 
        for (int i = 0; i < 4; i++) {
            int next_x = x + dir_x[i];
            int next_y = y + dir_y[i];
            int next_d = d + 1;
 
            if (next_x >= 0 && next_y >= 0 && next_x < c && next_y < r) {
                if (check[next_y][next_x] == 0 && map[next_y][next_x] == 0) {
                    check[next_y][next_x] = 1;
 
                    one_x[one_top] = next_x;
                    one_y[one_top] = next_y;
                    if (distance_list[next_d] == 0) // 거리의 시작 인덱스를 저장
                        distance_list[next_d] = one_top;
                    one_d[one_top++] = next_d;                    
                }
            }
        }
    }
}
 
void binary_search(int start, int end) {// 이진탐색
    if (start <= end) {
        int num = (start + end) / 2;
        int bigger = 0;
        int smaller = 0;
 
        for (int i = 0; i < zero_num; i++) { // 0지점들과 거리 비교
            for (int j = distance_list[num + 1]; j < one_top; j++) {
                int d = abs(zero_x[i] - one_x[j]) + abs(zero_y[i] - one_y[j]);
 
                if (d > num) {
                    bigger = 1;
                    break;
                }
            }
            if (bigger == 0) {
                smaller = 1;
                break;
            }
            bigger = 0;
        }
 
        if (smaller == 1) { // 왼쪽 부분 탐색
            k = num;
            binary_search(start, num - 1);
        }
        else { //오른쪽 부분 탐색
            binary_search(num + 1, end);
        }
    }
}
 
int main() {
    int T;
    int idx = 0;
 
    cin >> T;
 
    while (idx++ < T) {
        string s;
 
        cin >> r >> c;
 
        for (int i = 0; i < r; i++) {
            cin >> s;
            for (int j = 0; j < c; j++) {
                map[i][j] = s[j] - '0';
                if (map[i][j] == 1) {
                    one_x[one_top] = j;
                    one_y[one_top] = i;
                    one_d[one_top++] = 0;
                }
                else if(map[i][j] == 0) { // 나중에 거리비교를 위해 0인 지점의 정보들을 따로 저장
                    zero_x[zero_num] = j;
                    zero_y[zero_num++] = i;
                }
            }
        }
        if (zero_num <= 1) // 사무실을 하나 새로 건설하기 때문에 0이 한개 이하면 총 배달 시간은 0이 된다.
            cout << "Case  #" << idx << ": 0" << endl;
        else if (one_top == 0) { // 1이 하나도 없는 경우에는 가장 중간에 사무실을 건설
            map[r / 2][c / 2] = 1;
            one_x[one_top] = r/2;
            one_y[one_top] = c/2;
            one_d[one_top++] = 0;
 
            bfs();
 
            cout << "Case #" << idx << ": " << one_d[one_top - 1] << endl;
        }
        else {
            bfs();
 
            max_distance = one_d[one_top - 1];
            binary_search(1, max_distance);
 
            if(k != 0)
                cout << "Case #" << idx << ": " << k << endl;
            else
                cout << "Case #" << idx << ": " << max_distance << endl;
        }
 
        k = 0;
        one_top = 0;
        one_rear = 0;
        zero_num = 0;
        memset(check, 0, sizeof(check));
        memset(distance_list, 0, sizeof(distance_list));
    }
}

 

기존 bfs문제를 풀 때는 bfs만 적용하던가 완전탐색을 적용했을 때, 풀리는 경우가 대부분이었는데 역시 세계적인 대회이다 보니 문제의 난이도가 높은 것 같아요.

 

그래도 새로운 문제해결 방법을 알게되어서 기분이 좋습니다.

 

앞으로 더 열심히 해야겠습니다.ㅎㅎㅎ

 

다음 문제도 얼른 해결해서 포스팅하겠습니다. 감사합니다~

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!