2842번 집배원 한상덕

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

복습 bfs 생각 이분 탐색

bfs로 가중치가 더 작으면 갱신하는 방식으로 구현하려다가 반례가 바로 눈에 들어왔다.

핵심은 투포인터 + dfs이다.

또한, vector v에서 중복 원소를 없애는 것도 핵심이 될 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 52
 
int N, sy, sx, k;
int dy[8] = { 0, 1, 0, -1, -1, 1, 1, -1 };
int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 };
pair<char, int> m[Max][Max];
bool visit[Max][Max];
vector<int> v;
 
int dfs(int r, int c, int left, int right)
{
    if (m[r][c].second < v[left] || v[right] < m[r][c].second) return 0;
 
    int ret = 0;
    if (m[r][c].first == 'K') ++ret;
 
    for (int i = 0; i < 8; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
        if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x]) continue;
        visit[y][x] = true;
        ret += dfs(y, x, left, right);
    }
 
    return ret;
}
 
int main(void)
{
    cin.tie(0);
    int h, answer = INT32_MAX;
    char c;
    cin >> N;
 
    for (int i = 0; i < N; i++)    
        for (int j = 0; j < N; j++)
        {
            cin >> c;
            m[i][j].first = c;
            if (c == 'P') sy = i, sx = j;
            else if (c == 'K') ++k;
        }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &h);
            m[i][j].second = h;
            v.push_back(h);
        }
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    int left = 0, right = 0;
 
    while (left <= right)
    {        
        memset(visit, false, sizeof(visit));
 
        int get = dfs(sy, sx, left, right);
 
        if (get < k && right + 1 < v.size()) ++right;        
        else if (get == k) { answer = min(answer, v[right] - v[left]); ++left; }
        else break; // 다른 경우 존재할 수 없음. 즉, right가 v.size() 이상이거나 get과 k가 다르다면 이미 끝난 상황.
    }
 
    printf("%d\n", answer);
 
    return 0;
}