[BOJ] 9879 : Cross Country Skiing

문제 링크

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

9879번: Cross Country Skiing

그래프 탐색 문제

문제 해석

겨울 Moolympics 크로스 컨트리 종목 코스는 M x N 크기의 고도로 이루어진 좌표평면으로 나타낸다.

각 고도는 0부터 1,000,000,000 까지 가능하다.

좌표평면의 몇 칸은 waypoints로 정해져있다. Moolympic 의 주최자는 소들이(소가 참가자인듯) 모든 waypoints를 도달할 수 있게하는 고도의 차이 D의 최소를 구하려고 한다. 이동한 칸의 고도 차이가 최소가 되도록 모든 waypoints를 방문했을 때 고도의 차이가 최소 D는 돼야 모든 waypoints에 도달할 수 있다는 뜻이다. 인접한 네 방향 상하좌우로 이동할 수 있다. 이때 D의 최소를 찾아라.

풀이

이분탐색을 통해서 D 값을 지정해준다. 범위는 Left는 0, Right는 최대고도와 최소고도의 차이가 된다.

D 값은 mid값으로 지정해주고, BFS로 탐색하는데 고도의 차이가 mid보다 작거나 같은 칸으로만 이동할 수 있다. BFS 탐색을 모두 마친 후 모든 waypoints를 방문했다면 그때의 mid값은 유효한 값이 된다. 그러면 범위를 Left ~ mid - 1로 범위를 줄여서 더 작은 유효한 D값을 찾아본다. 이때 waypoint들 중에 임의의 한 지점을 시작점으로 입력한다.

나는 모든 waypoints를 방문했는지를 체크하기 위해서, 탐색 도중에 waypoints를 몇 군데 방문했는지 기록하고 탐색 종료 후에 모든 waypoint의 수와 방문한 waypoint의 수가 같으면 모든 waypoint를 방문했다고 판단했다.

#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 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 500 + 5;
int Map[MAX_N][MAX_N];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int N, M;
vector <pair<int, int>> waypoints;
bool is_waypoint[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
 
bool is_ok(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M)
        return false;
    return true;
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    int L = INF;
    int R = -1;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> Map[i][j];
            L = min(Map[i][j], L);
            R = max(Map[i][j], R);
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int num; cin >> num;
            if (num == 1) {
                waypoints.push_back({ i,j });
                is_waypoint[i][j] = true;
            }
        }
    }
    R = R - L;
    L = 0;
    int ans = INF;
    while (L <= R) {
        int mid = (L + R) / 2;
        queue<pair<int, int>> q;
        q.push(waypoints[0]);
        int cnt = 0;
        memset(visited, false, sizeof(visited));
        while (!q.empty()) {
            pair<int, int> now = q.front();
            q.pop();
            if (visited[now.first][now.second])
                continue;
            visited[now.first][now.second] = true;
            if (is_waypoint[now.first][now.second])
                cnt++;
            if (cnt == waypoints.size())
                break;
            for (int i = 0; i < 4; i++) {
                pair<int, int> next = { now.first + dy[i], now.second + dx[i] };
                if (is_ok(next.first, next.second)) {
                    int Diff = abs(Map[now.first][now.second] - Map[next.first][next.second]);
                    if (Diff > mid)
                        continue;
                    if (visited[next.first][next.second])
                        continue;
                    q.push(next);
                }
            }
        }
        if (cnt == waypoints.size()) {
            ans = min(ans, mid);
            R = mid - 1;
        }
        else L = mid + 1;
    }
    cout << ans << "\n";
    return 0;
}