[백준] Tractor

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

5846번: Tractor

BFS를 이용한 flood fill과 이진탐색이 사용되는 문제입니다.

 

문제부터 간단히 이야기를 해보면, 

비용 D 짜리 트랙터를 사면, 이웃한 field의 높이차이가 D까지만 돌아다닐 수 있고, 그 이상은 돌아다닐 수 없습니다. 우리는 이 D를 최소로 하여, John이 field의 반 이상을 돌아다닐 수 있게 해주고 싶습니다. 

 

이 때의 D를 구하는 것이 문제입니다.

 

<Solution>

D를 어떻게 구해야 하는지 생각해보면, D를 바꾸면서 탐색을 해보는 것이 가장 나은 방법이라는 것을 생각 해 볼 수 있습니다.

 

하지만 모든 D에 대해 탐색하면 너무 시간이 오래 걸릴 것이므로, D의 최소와 최대를 먼저 생각해서 이것에 대해 이진탐색을 하며 조사하면 됩니다.

 

실제 코드는 아래와 같습니다.

#include <iostream>
#include <queue>
 
struct rc{
    int r, c;
};
 
using namespace std;
 
// 최소 성능을 기준으로 binary search 하면 됨
 
int N;
int grids[500+10][500+10];
int visited[500+10][500+10];
int half;
 
int d_row[] = {1, -1, 0, 0};
int d_col[] = {0, 0, 1, -1};
 
int counter;
 
void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cin >> grids[i][j];
        }
    }
}
int abs(int k){
    return (k>=0)? k : -k;
}
 
void fill(int r, int c, int mid){
    // bfs로 채우자
    queue <rc> q;
    q.push((rc){r,c});
    visited[r][c]=1;
    counter ++;
 
    while(!q.empty()){
        rc cur = q.front(); q.pop();
 
        for(int i=0;i<4; i++){
            int new_r = cur.r + d_row[i];
            int new_c = cur.c + d_col[i];
 
            if(!(0<= new_r && new_r <N && 0<= new_c && new_c <N)) continue;
            if(abs(grids[new_r][new_c] - grids[cur.r][cur.c]) > mid) continue;
            if(visited[new_r][new_c]) continue;
 
            q.push((rc){new_r,new_c});
            visited[new_r][new_c] = 1;
            counter ++;
        }
    }
}
 
bool is_possible(int mid){
    // D -> mid 인 상황 half 이상 방문이 가능한지 확인해야함.
    // visited 초기화
    for(int i= 0; i<500+10; i++){
        for(int j = 0; j<500+10; j++){
            visited[i][j] = 0;
        }
    }
 
    for(int i = 0; i<N; i++){
        for (int j =0; j<N; j++){
            if(visited[i][j]) continue;
            counter = 0;
            fill(i,j, mid);
            if(counter >=half) return true;
        }
    }
    return false;
 
 
}
 
int bs(int s, int e){
 
    int sol = -1;
 
    while(e>=s){
        int mid = (e+s)/2;
        if(is_possible(mid)){
            e = mid-1;
            sol = mid;
 
        }
        else{
            s = mid+1;
        }
 
    }
    return sol;
}
 
int solution(){
    half = N*N/2 + N*N%2;
    int s=0;
    int e=0;

    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            e = max(e, grids[i][j]);

        }
    }
 
    return bs(s, e);
 
}
 
int main(){
    int ans = -1;
 
    InputData();
 
    ans = solution();
 
    cout <<  ans << endl;
    return 0;
}