[BOJ] 2842 : 집배원 한상덕

문제 링크

2842번: 집배원 한상덕 (acmicpc.net)

2842번: 집배원 한상덕

투포인터와 BFS가 합쳐진 재밌는 문제였다.

 

참고 링크

https://dar0m.tistory.com/77

[C++] vector 배열 중복 제거 하는 법

벡터에서 중복을 제거하는 법을 까먹어서 다른 분의 게시물을 참고하면서 코드를 짰다.

 

풀이

< 준비물 >

1. 들러야 할 집이 총 몇 군데인지 센다.

2. 우체국의 좌표를 저장한다.

3. 모든 고도를 다 저장하고 정렬한 후 중복을 제거한다.

벡터에 저장한 후 unique() 함수를 이용해서 중복을 제거할 수 있다.

일단 입력을 받으면서 이 3가지를 준비해야한다.

여기서 고도가 저장된 벡터를 H 벡터라고 하자.

3
P..
.KK
...
3 2 4
7 4 2
2 3 1​

제시된 예제3을 예로 들면, H 벡터에는 중복을 제거 한 { 1 2 3 4 7 } 이 들어있을 것이다. 이 벡터를 이용해서 집배원이 이용할 칸의 고도의 범위를 설정한다. 범위를 설정한 후 BFS 를 이용해서 집배원이 모든 우편을 배달 할 수 있는 지를 판별한다.

판별 : BFS를 돌면서 방문한 집의 수가 총 집의 수와 같아지면 모든 우편 배달을 성공한 것이다.

 

갈 수 있는 고도의 범위를 H[left] ~ H[right] 까지라고 하면, 초기값은 left = 0, right = 0 으로 설정해준다.

1. 설정한 범위 내에서 집배원이 모든 우편을 배달 할 수 있으면 left를 늘려서 범위를 좁혀준다.

2. 설정한 범위 내에서 집배원이 모든 우편을 배달하지 못한다면 right를 늘려서 범위를 늘려준다.

이 과정을 반복하면서 모든 우편을 배달 할 수 있는 가장 좁은 범위를 찾으면 된다. 고도의 범위가 가장 좁다는 것은 가장 높은 고도와 가장 낮은 고도의 차이가 가장 적다는 뜻이기 때문이다. 

※ 주의할 점

BFS를 탐색하기 전에 우체국의 고도가 설정한 범위 내에 들어있을 때 BFS 탐색을 시작한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 50 + 5;
int dx[] = { 0,1,0,-1, 1,-1,1,-1 };
int dy[] = { 1,0,-1,0, -1,1,1,-1 };
char Map[MAX_N][MAX_N];
int height[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
vector<int> H;
int N, K;
bool is_ok(pair<int, int>);
bool BFS(pair<int, int> st, pair<int,int> Range);
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    pair<int, int> Post;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> Map[i][j];
            if (Map[i][j] == 'P')
                Post = { i,j };
            else if (Map[i][j] == 'K')
                K++;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> height[i][j];
            H.push_back(height[i][j]);
        }
    }
    sort(H.begin(), H.end());
    H.erase(unique(H.begin(), H.end()), H.end());
    int left = 0;
    int right = 0;
    int ans = INF;
    while (right < H.size()) {
        while (true) {
            if (height[Post.first][Post.second] > H[right]
                || height[Post.first][Post.second] < H[left])
                break;
            memset(visited, false, sizeof(visited));
            if (BFS(Post, { H[left],H[right] })) {
                ans = min(ans, H[right] - H[left]);
            }
            else break;
            left++;
        }
        right++;
    }
    cout << ans << "\n";
    return 0;
}
bool BFS(pair<int, int> st, pair<int,int> Range) {
    queue<pair<int, int>> q;
    q.push({ st.first,st.second });
    visited[st.first][st.second] = true;
    int cnt = 0;
    while (!q.empty()) {
        pair<int, int> now = q.front();
        q.pop();
        if (Map[now.first][now.second] == 'K') {
            cnt++;
            if (cnt == K) return true;
        }
        for (int i = 0; i < 8; i++) {
            pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
            if (is_ok(next)) {
                if (height[next.first][next.second] >= Range.first && height[next.first][next.second] <= Range.second) {
                    q.push(next);
                    visited[next.first][next.second] = true;
                }
            }
        }
    }
    return false;
}
 
bool is_ok(pair<int, int> now) {
    if (now.first < 0 || now.first >= N || now.second < 0 || now.second >= N || visited[now.first][now.second])
        return false;
    return true;
}