[백준] 2842: 집배원 한상덕

0. 문제 주소

 

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

2842번: 집배원 한상덕

 

 

1. 풀이

 

알고리즘 분류가 "이분 탐색"이라고 되어 있는 것을 보고 처음에 생각난 풀이는 다음과 같다.

 

0. 집들과 우체국이 있는 위치의 고도 중 가장 낮은 고도를 min_H, 가장 높은 고도를 max_H라고 하자.

 

1. 먼저 방문 가능한 고도의 최대값을 MAX = 1,000,000으로 설정하고, 0 ~ min_H 사이의 값에 대해

모든 K와 P가 방문 가능한 최대의 값을 이분 탐색을 이용해 찾는다.

 

2. 이번에는 방문 가능한 고도의 최소값을 1.에서 찾은 값으로 설정해두고, max_H ~ MAX 사이의 값에 대해

모든 K와 P가 방문 가능한 최소의 값을 이분 탐색을 이용해 찾는다.

 

 

#include <bits/stdc++.h>
#define MAX 53
#define INF 1000001
#define ll long long
#define pii pair<int, int>

using namespace std;

int N;
int grid[MAX][MAX];
int disc[MAX][MAX];
int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool visited[MAX][MAX];
vector<pii> houses;
int start_i, start_j;

void debug(){
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cout << disc[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool check(){
    for (auto p: houses){
        if (!visited[p.first][p.second]) return false;
    }
    return true;
}

void make_disc(int m, int M){
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (grid[i][j] < m || grid[i][j] > M){
                visited[i][j] = true;
            }
            else{
                disc[i][j] = grid[i][j];
            }
        }
    }
}

void BFS(int x, int y){
    queue<pii> q;
    q.push(pii(x, y));
    visited[x][y] = true;

    while(!q.empty()){
        pii p = q.front();
        q.pop();
        int ci = p.first, cj = p.second;
        for (int d=0;d<8;d++){
            int ni = ci + di[d], nj = cj + dj[d];
            if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
            if (visited[ni][nj]) continue;
            visited[ni][nj] = true;
            q.push(pii(ni, nj));
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;

    for (int i=0;i<N;i++){
        string row;
        cin >> row;
        for (int j=0;j<N;j++){
            if (row[j] == 'K') {
                houses.push_back(pii(i, j));
            }
            else if (row[j] == 'P'){
                start_i = i;
                start_j = j;
            }
        }
    }

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            int temp;
            cin >> temp;
            grid[i][j] = temp;
        }
    }


    int house_min = INF, house_max = 0;

    for (auto p: houses){
        int curr = grid[p.first][p.second];
        house_min = min(curr, house_min);
        house_max = max(curr, house_max);
    }

    int l = 0, r = house_min, mid = (l+r) / 2;

    while(l+1 < r){
        memset(visited, 0, sizeof(visited));
        make_disc(mid, INF);
        BFS(start_i, start_j);
        if (check()) {
            l = mid;
        }
        else{
            r = mid;
        }
        mid = (l+r) / 2;
    }

    int ans_min = mid+1;

    l = house_max, r = INF, mid = (l+r) / 2;

    while(l+1 < r){
        memset(visited, 0, sizeof(visited));
        make_disc(ans_min, mid);
        BFS(start_i, start_j);
        if (check()){
            r = mid;
        }
        else{
            l = mid;
        }
        mid = (l+r) / 2;
    }

    int ans_max = mid;

    cout << ans_max - ans_min;



    return 0;
}

 

 

시원하게 틀렸다.

 

 

위에서 찾은 최소, 최대 고도를 각각 ans_min , ans_max라고 해보자.

일단 이 값들은 ans_min <= min_H , max_H <= ans_max를 만족할 것이다.

하지만 (ans_min, ans_max) 순서쌍만이 모든 K와 P를 방문할 수 있는 순서쌍은 아니다.

더불어, 차이가 최소가 되는 일도 반드시 일어나지는 않는다.

 

고도의 최솟값이 될 수 있는 값을 먼저 찾았기 때문에,

 

"고도의 최솟값은 조금 낮더라도, 고도의 최댓값을 더 낮게 하면서 여전히 모든 K와 P를 방문할 수 있는 경우"가 있기 때문이다. 아래 반례를 보자.

 

 

 

ans_min을 이분탐색으로 찾는다 :  0부터 5까지 값 중 모든 K와 P를 방문할 수 있으면 탐색값을 올린다.

때문에 ans_min값은 5가 되었고,

 

 

ans_max를 이분탐색으로 찾는다 : 7부터 MAX 중 모든 K와 P를 방문할 수 있으면 탐색값을 내린다.

때문에 ans_max는 11이 되었다.

 

 

하지만 위에 언급한대로

"고도의 최솟값은 조금 낮더라도, 고도의 최댓값을 더 낮게 하면서 여전히 모든 K와 P를 방문할 수 있는 경우"가

위 예시의 정답이다.

 

 

 

이러한 반례를 찾아내고 사용한 다른 풀이는 다음과 같다.

 

 

0. 제시된 모든 고도값들을 저장해두고 정렬한다.

1. 투포인터를 이용해, L = 고도의 최솟값, R = 고도의 최댓값으로 탐색하며

  1-1. L과 R이 가리키는 최소, 최댓값으로 모든 K와 P를 방문할 수 있으면 L을 오른쪽으로 이동시킨다.

  1-2. 방문할 수 없으면, R을 오른쪽으로 이동시킨다.

2. 1.에서 가능한 모든 경우들 중 피로도가 가장 작은 경우가 답이다.

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 53
#define INF 1000001
#define ll long long
#define pii pair<int, int>

using namespace std;

int N;
int grid[MAX][MAX];
int disc[MAX][MAX];
int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};
bool visited[MAX][MAX];
vector<pii> houses;
vector<int> H;
int start_i, start_j;

void debug(){
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cout << disc[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool check(){
    for (auto p: houses){
        if (!visited[p.first][p.second]) return false;
    }
    return true;
}

void make_disc(int m, int M){
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (grid[i][j] < m || grid[i][j] > M){
                disc[i][j] = -1;
            }
            else{
                disc[i][j] = grid[i][j];
            }
        }
    }
}

void BFS(int x, int y){
    if (disc[x][y] == -1) return;
    queue<pii> q;
    q.push(pii(x, y));
    visited[x][y] = true;

    while(!q.empty()){
        pii p = q.front();
        q.pop();
        int ci = p.first, cj = p.second;
        for (int d=0;d<8;d++){
            int ni = ci + di[d], nj = cj + dj[d];
            if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
            if (visited[ni][nj]) continue;
            if (disc[ni][nj] == -1) continue;
            visited[ni][nj] = true;
            q.push(pii(ni, nj));
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;

    for (int i=0;i<N;i++){
        string row;
        cin >> row;
        for (int j=0;j<N;j++){
            if (row[j] == 'K') {
                houses.push_back(pii(i, j));
            }
            else if (row[j] == 'P'){
                houses.push_back(pii(i, j));
                start_i = i;
                start_j = j;
            }
        }
    }

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            int temp;
            cin >> temp;
            grid[i][j] = temp;
            H.push_back(temp);
        }
    }

    sort(H.begin(), H.end());
    int H_size = H.size();

    int l = 0, r = 0;
    int ans = INF;;

    while(l < H.size() || r < H.size()){
        memset(visited, 0, sizeof(visited));
        make_disc(H[l], H[r]);
        BFS(start_i, start_j);
        if (!check()){
            if (r == H.size() - 1){
                break;
            }
            r++;
        }
        else{
            ans = min(ans, H[r] - H[l]);
            l++;
        }
    }

    cout << ans << endl;

    return 0;
}