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

 

이 글은 한국 시간으로 2019년 3월 24일 오후 1시에 치뤄진  Google Kick Start 2019 Round A에 나온 문제에 대해서 다룹니다.

 

problem B : Parcles

---

Q. 격자로 표현된 지도(r X c)에 파르셀을 배달하는 지점들이 있다. 이 지도에 지점을 하나 더 세워서 고객들에게 파르셀을 배송할 때, 모든 고객에게 배송될 수 있는 최소시간을 구하시오. 단, 지도는 입력으로 주어지며, 지점은 1, 고객은 0으로 표현되고 새로운 지점은 0에 세울 수 있다. 배달 시간은 가장 가까운 지점과의 거리( |r1-r2| + |c1-c2|)로 정의된다. 

처음, 이 문제를 접근 할 때, bfs에 완전탐색을 접목하는 방향으로 문제를 해결하려 했습니다. 모든 0을 1로 치환한 다음 bfs를 적용한 다음, 원하는 답을 찾는 것이지요. 이 접근방법에 대한 코드입니다.

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
 
using namespace std;
 
int map[250][250];
int check[250][250];
int r, c;
int minimum = 500;
int checking = 0;
 
int zero_x[62500];
int zero_y[62500];
int zero_top = 0;
 
int one_x[62500];
int one_y[62500];
int d1[62500];
int one_top = 0;
int one_rear = 0;
 
int dir_x[4] = { 1,0,-1,0 };
int dir_y[4] = { 0,1,0,-1 };
 
void bfs() {
 
    while (one_rear < one_top) {
        int x = one_x[one_rear];
        int y = one_y[one_rear];
        int d = d1[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_x < c && next_y >= 0 && 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;
                    d1[one_top++] = next_d;
 
                    if (next_d >= minimum) {
                        checking = 1;
                        return;
                    }
                }
            }
        }
    }
}
int main() {
    int T;
    int idx = 0;
 
    cin >> T;
 
    while (idx++ < T) {
        cin >> r >> c;
 
        for (int i = 0; i < r; i++) {
            string s;
 
            cin >> s;
 
            for (int j = 0; j < c; j++) {
                map[i][j] = s[j] - '0';
 
                if (map[i][j] == 0) {
                    zero_x[zero_top] = j;
                    zero_y[zero_top++] = i;
                }
                if (map[i][j] == 1) {
                    one_x[one_top] = j;
                    one_y[one_top] = i;
                    d1[one_top++] = 0;
                }
            }
        }
 
        if (zero_top <= 1) { // 새로운 office를 세우기 때문
            cout << "Case  #" << idx << ": " << "0" << endl;
        }
        else {
            int num = one_top;
 
            for (int i = 0; i < zero_top; i++) { // 완전탐색 모든 '0'이 '1'의 후보가 됨
                one_x[one_top] = zero_x[i];
                one_y[one_top] = zero_y[i];
                d1[one_top] = 0;
                map[one_y[one_top]][one_x[one_top++]] = 1;
 
                bfs();
 
                if (checking == 0)
                    minimum = min(minimum, d1[one_top - 1]);
 
                map[one_y[num]][one_x[num]] = 0;
                one_top = num;
                one_rear = 0;
                checking = 0;
                memset(check, 0, sizeof(check));
            }
 
            cout << "Case #" << idx << ": " << minimum << endl;
        }
        minimum = 500;
        zero_top = 0;
        one_top = 0;
        one_rear = 0;
    }
}

 

이 코드는 visible 테스트 케이스를 통과하기에는 충분했지만, hidden 테스트 케이스는 time limit을 만족하지 못합니다. 

이 방향을 유지하며 time limit을 만족하기 위해 코드를 수정하고 또 수정했는데 실패했습니다.

Kick Start는 친절하게도 대회가 끝나고 나면 문제와 해결 방법을 오픈 합니다.

그래서 저는 해결방법을 참고해 코드를 수정했는데, 다음 글에서 소개하겠습니다.