[백준]#9879 Cross Country Skiing

문제

The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 <= M,N <= 500), each elevation being in the range 0 .. 1,000,000,000.

Some of the cells in this grid are designated as waypoints for the course. The organizers of the Moolympics want to assign a difficulty rating D to the entire course so that a cow can reach any waypoint from any other waypoint by repeatedly skiing from a cell to an adjacent cell with absolute elevation difference at most D. Two cells are adjacent if one is directly north, south, east, or west of the other. The difficulty rating of the course is the minimum value of D such that all waypoints are mutually reachable in this fashion.

입력

• Line 1: The integers M and N.
• Lines 2..1+M: Each of these M lines contains N integer elevations.
• Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, with 1 indicating a cell that is a waypoint.

출력

• Line 1: The difficulty rating for the course (the minimum value of D such that all waypoints are still reachable from each-other).

예제 입력 1

3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

예제 출력 1

21

풀이

이 문제는 bfs(너비 우선 탐색), 이분탐색 알고리즘을 이용해서 풀 수 있었다. 이분탐색을 통해 가능한 D값을 구하고 해당 D값으로 모든 waypoint를 갈 수 있는 지 체크했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static ArrayList<Integer> points;
    static HashSet<Integer> set;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        map = new int[N][M];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");

            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(input[j]);
                min = Math.min(min, map[i][j]);
                max = Math.max(max, map[i][j]);
            }
        }

        points = new ArrayList<>();
        for(int i=0; i<N; i++) {
            input = br.readLine().split(" ");
            for(int j=0; j<M; j++) {
                if(Integer.parseInt(input[j])==1) {
                    points.add(i*M+j);
                }
            }
        }

        int left = 0;
        int right = max-min+1;
        int ans = -1;

        while(left <= right) {          //가능한 D값 중에서 최소 이분 탐색
            int mid = (left+right)/2;
            set = new HashSet<>();
            int start = points.get(0);
            boolean flag = true;

            bfs(start/M, start%M, mid);

            for(int i=0; i<points.size(); i++) {
                int point = points.get(i);

                if(!set.contains(point)) {
                    flag = false;
                    break;
                }
            }

            if(!flag) {
                left = mid+1;
            }

            else {
                right = mid-1;
                ans = mid;
            }
        }

        System.out.println(ans);
    }

    public static void bfs(int x, int y, int D) {       //정해진 D를 이용해서 갈 수 있는 포인트 모두 찾음
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        set.add(x*M+y);
        queue.add(new Point(x, y));
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            Point temp = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];

                if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny] || Math.abs(map[nx][ny]-map[temp.x][temp.y])>D) continue;

                visited[nx][ny] = true;
                set.add(nx*M+ny);
                queue.add(new Point(nx, ny));
            }
        }
    }

    public static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}