[2842] 집배원 한상덕

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

2842번: 집배원 한상덕

<문제>

구간 [l, r]를 전달하여 모든 집을 방문할 수 있는지를 bool형으로 리턴하는 bfs를 구현해둔다.

입력된 고도 전부를 vector에 넣어주고, 오름차순 정렬&&중복제거를 진행해준다.

이후에 투포인터를 적용하여 최대 N^2개의 원소를 갖는 vector를 O(N)동안 순회한다.

하나의 bfs당 걸리는 시간은 약 1만, (N^3)*1만 == 125'000'000, 제한시간이 3초이므로 충분하다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, kNum, sy, sx, a[53][53], dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
                                dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
char Map[53][53];
vector<pair<int, int>> endPos;
typedef struct {
    int y, x;
} state;
bool bfs(int l, int r) {
    if ((l <= a[sy][sx] && a[sy][sx] <= r) == 0) return false;
    queue<state> q;
    q.push({sy, sx});
    bool visited[51][51];
    memset(visited, 0, sizeof(visited));
    visited[sy][sx] = true;
    int i, cnt = 0;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cnt == kNum) return true;
        for (i = 0; i < 8; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= n) continue;
            if (visited[y][x]) continue;
            if (l <= a[y][x] && a[y][x] <= r) {
                visited[y][x] = true;
                if (Map[y][x] == 'K') cnt++;
                q.push({y, x});
            }
        }
    }
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            cin >> Map[i][j];
            if (Map[i][j] == 'P') {
                sy = i;
                sx = j;
            } else if (Map[i][j] == 'K')
                kNum++;
        }
    }
    vector<int> v;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> a[i][j];
            v.push_back(a[i][j]);
        }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sort(v.begin(), v.end());
    int S = v.size();
    int left = 0, right = 0, ans = 1e9;
    while (left < S) {
        bool ret = bfs(v[left], v[right]);
        if (ret == true) {
            int score = v[right] - v[left];
            ans = min(score, ans);
            left++;
        } else {
            right++;
            if (right == S) break;
        }
    }
    cout << ans;
    return 0;
}