백준 1486 등산 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/1486

1. 2차원 배열 MAP이 주어진다. (i,j) 좌표에는 해당 좌표의 고도가 주어진다.

2. (0,0)은 호텔이 있는 지점이다. 호텔에서부터 다른 좌표의 고도를 탐방할 예정인데, 다음 규칙을 지킨다.
1. 현 고도 >= 넘어갈 고도 이면 시간이 1초 소모
2. 현 고도 < 넘어갈 고도 이면 $( \text{넘어갈 고도} - \text(현 고도) )^{2}$ 초가 든다.
3. D라는 시간제한이 주어지고 이 시간안에 호텔로 다시 돌아와야 한다.

3. 세준이가 호텔을 떠나서 다시 되돌아올 때까지 건널 수 있는 가장 높은 고도는 얼마인가?

(1) 조건 분석 📊

2. 코드가 나오기까지 🛠️

(1) 4차원 배열 이용 모든 (시작,도착) 경우의 수의 다익스트라 다 구하기

(2) 다익스트라 딱 두 번으로 구하기

1. (0,0) 출발 - 모든 점까지 도착을 다익스트라로 구하기

2. 모든 점 출발 - (0,0) 도착을 다익스트라로 구하기

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

A. 1번 풀이

import java.util.*;
import java.io.*;

// 1486 등산
public class Main {
    static class Coor{
        int r;
        int c;
        int t;

        public Coor(int r, int c, int t){
            this.r = r;
            this.c = c;
            this.t = t;
        }
    }
    static int R,C,H,D;
    static int [][] map;
    static int [][][][] dp;
    static int [][] dir = new int [][] {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        map = new int [R][C];
        dp = new int [R][C][R][C];
        for(int i = 0; i < R; i++){
            String row = br.readLine();
            for(int j = 0; j < C; j++){
                int h = row.charAt(j);
                if(65 <= h && h <= 90) h -= 65;
                if(97 <= h && h <= 122) h -= 71;
                map[i][j] = h;
            }
        }
        for(int i = 0; i < R; i++){
            for(int j = 0; j < C; j++){
                for(int k = 0; k < R; k++){
                    Arrays.fill(dp[i][j][k], 1_000_001);
                }
            }
        }

        for(int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                dijkstra(i,j);
            }
        }
        int max = 0;
        for(int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                if(dp[0][0][i][j] + dp[i][j][0][0] <= D) max = Math.max(max, map[i][j]);
            }
        }
        System.out.printf("%d", max);
    }

    public static void dijkstra(int r, int c){
        PriorityQueue<Coor> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.t));
        pq.add(new Coor(r,c,0));
        dp[r][c][r][c] = 0;

        while (!pq.isEmpty()){
            Coor now = pq.poll();
            if(now.t > dp[r][c][now.r][now.c]) continue;
            for(int i = 0; i < 4; i++){
                int nr = now.r + dir[i][0];
                int nc = now.c + dir[i][1];
                if(OOB(nr,nc)) continue;
                if(Math.abs(map[now.r][now.c] - map[nr][nc]) > H) continue;
                int spend_time = map[now.r][now.c] >= map[nr][nc]? 1 : (int) Math.pow(map[now.r][now.c]-map[nr][nc],2);
                if(now.t + spend_time >= dp[r][c][nr][nc]) continue;
                if(now.t + spend_time > D) continue;
                dp[r][c][nr][nc] = now.t + spend_time;
                pq.add(new Coor(nr,nc,dp[r][c][nr][nc]));
            }
        }
    }

    public static boolean OOB (int r, int c){
        return r < 0 || c < 0 || r >= R || c >= C;
    }

}

B. 2번 풀이

import java.util.*;
import java.io.*;
import java.util.function.Function;

// 1486 등산
public class Main {
    static class Coor{
        int r;
        int c;
        int t;

        public Coor(int r, int c, int t){
            this.r = r;
            this.c = c;
            this.t = t;
        }
    }
    static int R,C,H,D;
    static int [][] map;
    static int [][] dir = new int [][] {{0,1}, {0,-1}, {1,0}, {-1,0}};
    static int [][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        map = new int [R][C];
        dp = new int[R][C][2];
        for(int i = 0; i < R; i++){
            String row = br.readLine();
            for(int j = 0; j < C; j++){
                int h = row.charAt(j);
                if(65 <= h && h <= 90) h -= 65;
                if(97 <= h && h <= 122) h -= 71;
                map[i][j] = h;
            }
        }
        for(int i = 0; i < R; i++){
            for(int j = 0; j < C; j++){
                dp[i][j][0] = 1_000_001;
                dp[i][j][1] = 1_000_001;
            }
        }
        dp[0][0][0] = 0;
        dp[0][0][1] = 1;
        dijkstra(0, (prevR, prevC, nowR, nowC) -> (map[prevR][prevC] >= map[nowR][nowC]? 1 : (int)Math.pow(map[prevR][prevC]-map[nowR][nowC], 2)));
        dijkstra(1, (prevR, prevC, nowR, nowC) -> (map[prevR][prevC] <= map[nowR][nowC]? 1 : (int)Math.pow(map[prevR][prevC]-map[nowR][nowC], 2)));

        int max = 0;
        for(int i = 0; i < R; i++){
            for(int j = 0; j < C; j++){
                if(dp[i][j][0] + dp[i][j][1] <= D) max = Math.max(max, map[i][j]);
            }
        }
        System.out.println(max);
    }
    public static void dijkstra (int dimension, CalculateDistance calculateDistance ) {
        PriorityQueue<Coor> pq = new PriorityQueue<>(Comparator.comparingInt(o-> o.t));
        pq.add(new Coor(0,0, 0));
        while (!pq.isEmpty()){
            Coor now = pq.poll();
            if(now.t > dp[now.r][now.c][dimension]) continue;
            for(int i = 0; i < 4; i++){
                int nr = now.r + dir[i][0];
                int nc = now.c + dir[i][1];
                if(OOB(nr, nc)) continue;
                if(Math.abs(map[now.r][now.c] - map[nr][nc]) > H) continue;
                int spending_time = calculateDistance.cal(now.r, now.c, nr, nc);
                if(now.t + spending_time >= dp[nr][nc][dimension]) continue;
                dp[nr][nc][dimension] = now.t+spending_time;
                pq.add(new Coor(nr,nc, dp[nr][nc][dimension]));
            }
        }
    }

    public static boolean OOB(int r, int c){
        return r < 0 || c < 0 || r >= R || c >= C;
    }

    @FunctionalInterface
    public interface  CalculateDistance{
        Integer cal(int prevR, int prevC, int nowR, int nowC);
    }
}

4. 트러블 슈팅 or 배운 점📝