백준 22116 (창영이와 퇴근) - java

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

22116번: 창영이와 퇴근

 

문제

창영이의 퇴근길은 출근길과 조금 다르다. 창영이는 건강을 위해 따릉이를 빌려 타고 퇴근하는 습관을 기르고 있다.

창영이의 퇴근길은 N×N 크기의 격자로 표현된다. 창영이는 A1,1에서 출발하여 AN,N까지 이동할 계획이다. 창영이는 상하좌우 인접한 격자로 한 번에 한 칸씩 이동할 수 있다. 각 격자 Ar,c에는 자연수가 적혀 있는데, 이는 해당 지역의 높이를 뜻한다. 인접한 격자 사이의 높이 차이의 절댓값을 경사라고 하고, 경사가 클수록 경사가 가파르다고 하자.

따릉이는 가격에 따라 성능이 다르다. 비싼 따릉이는 경사가 가파르더라도 내리지 않고 타고 갈 수 있지만, 값싼 따릉이는 경사가 가파르면 힘들고 위험하기 때문에 내려서 이동해야 한다.

창영이는 최소한의 비용으로 따릉이를 빌려서, 따릉이에서 한 번도 내리지 않고 집에 도착하고 싶다. 그러기 위해선 창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다. 여러분들이 창영이를 도와주자.

 

유형 : 다익스트라

 

접근 방식

• 경사의 값을 최소로 유지한 채 탐색을 완료해야 하는 문제이다.
• 이전까지의 경로에 있어 가장 적은 경사 값으로만 탐색하고 있는 노드를 우선 탐색해야 한다.
  • 우선순위 큐를 이용한 다익스트라 !
• 방문 배열에 MAX값을 저장하고 탐색을 진행하자
  • 해당 값보다 적은 경사를 유지한채 도착했다면 갱신해주도록 하자

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int n = 0;
    static int m = 0;
    static int[][] board;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1;j<=n;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        search();

        br.close();
    }

    static void search(){
        int MAX = Integer.MAX_VALUE;

        int[][] v = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                v[i][j] = MAX;
            }
        }

        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> x.num - y.num
        );
        v[1][1] = 0;
        pq.add(new Node(1,1,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(cur.x == n && cur.y == n){
                break;
            }

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

                if(nx < 1 || nx > n || ny < 1 || ny > n)
                    continue;

                int tmp = Math.abs(board[nx][ny] - board[cur.x][cur.y]);

                if(v[nx][ny] > Math.max(v[cur.x][cur.y],tmp)){
                    v[nx][ny] = Math.max(v[cur.x][cur.y],tmp);
                    pq.add(new Node(nx,ny,v[nx][ny]));
                }
            }
        }

        System.out.println(v[n][n]);
    }
}
class Node{
    int x;
    int y;
    int num;

    Node(int x,int y,int num){
        this.x = x;
        this.y = y;
        this.num = num;
    }
}