백준 1486 (등산) - java

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

1486번: 등산

 

문제

세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다.

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다.

세준이의 호텔은 (0,0)에 있다. 그리고, 세준이는 지금 위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다.

만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이가 5에서 높이가 9인 곳으로 간다면, 시간은 (5-9)2=16초가 걸린다. 하지만, 높이가 9인 곳에서 5인 곳으로 간다면 시간은 1초가 걸린다.

산의 지도와, T, 그리고 어두워지는 시간 D가 주어졌을 때, 세준이가 D보다 크지 않은 시간 동안 올라갈 수 있는 최대 높이를 구하는 프로그램을 작성하시오.(세준이는 호텔에서 출발해서 호텔로 돌아와야 한다.)

 

유형 : 다익스트라

 

접근 방식

• 세준이는 호텔에서 출발해서 다시 호텔로 돌아와야 한다.
• 이 문제는 다익스트라를 2번 사용해서 풀 수 있다.
  • 처음에는 (0,0) -> (n,m)으로 올라가는 과정
  • 두 번째는 (n,m) -> (0,0)으로 과는 과정
• 구현 방법은 간단하다. 간선의 정보를 반대로 하면 된다. 처음에 올라가는 간선을 두번째 탐색때는 반대로 설정하면 된다.
• 즉 높이 차이가 높은곳에 낮은 곳으로 가는 것을 처음 탐색때는 1로 설정하지만 두번째 탐색때는 제곱 차이값으로 해야 한다.

주의할점이 높이가 같은 곳간의 이동은 첫번째 탐색이나 두번째 탐색 모두 1이다. -> 이것 때문에 10번을 박았다 ㅜㅡㅜ

 

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;
    static int k = 0;
    static int d = 0;

    static int[][] board;

    static int[][] tmpDis;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

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

        for(int i = 0 ; i < n ; i++){
            char[] arr = br.readLine().toCharArray();

            for(int j = 0 ; j < m ; j++){
                if(arr[j] >= 'A' && arr[j] <= 'Z'){
                    board[i][j] = arr[j] - 'A';
                }

                else{
                    board[i][j] = arr[j] - 'a' + 26;
                }
            }
        }

        bfs();
        bfs2();

        int result = board[0][0];

        for(int i = 0 ; i <  n ; i++){
            for(int j = 0; j < m ; j++){

                if(tmpDis[i][j] <= d){
                    result = Math.max(result,board[i][j]);
                }
            }
        }

        System.out.println(result);
        br.close();
    }

    static void bfs(){
        int result = 0;
        Queue<int[]> q = new ArrayDeque<>();
        int[][] dis = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                dis[i][j] = d + 1;
            }
        }

        dis[0][0] = 0;
        q.add(new int[]{0,0,0});

        while(!q.isEmpty()){
            int[] cur = q.poll();

            if(dis[cur[0]][cur[1]] < cur[2])
                continue;

            dis[cur[0]][cur[1]] = cur[2];

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;

                if(Math.abs(board[nx][ny] - board[cur[0]][cur[1]]) > k)
                    continue;

                if(board[nx][ny] > board[cur[0]][cur[1]]){
                    int tmpDis = Math.abs(board[nx][ny] - board[cur[0]][cur[1]]);
                    tmpDis = tmpDis * tmpDis;

                    int next = dis[cur[0]][cur[1]] + tmpDis;

                    if(next > d)
                        continue;

                    if(dis[nx][ny] > next){
                        dis[nx][ny] = next;
                        q.add(new int[]{nx,ny,dis[nx][ny]});
                    }

                }else{

                    if(dis[cur[0]][cur[1]] + 1 > d)
                        continue;

                    if(dis[nx][ny] > dis[cur[0]][cur[1]] + 1) {
                        dis[nx][ny] = dis[cur[0]][cur[1]] + 1;
                        q.add(new int[]{nx,ny,dis[nx][ny]});
                    }
                }
            }
        }

        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                tmpDis[i][j] += dis[i][j];
            }
        }
    }

    static void bfs2(){
        int result = 0;

        Queue<int[]> q = new ArrayDeque<>();
        int[][] dis = new int[n][m];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                dis[i][j] = d + 1;
            }
        }

        dis[0][0] = 0;
        q.add(new int[]{0,0,0});

        while(!q.isEmpty()){
            int[] cur = q.poll();

            if(dis[cur[0]][cur[1]] < cur[2])
                continue;

            dis[cur[0]][cur[1]] = cur[2];

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                    continue;

                if(Math.abs(board[nx][ny] - board[cur[0]][cur[1]]) > k)
                    continue;

                if(board[nx][ny] < board[cur[0]][cur[1]]){
                    int tmpDis = Math.abs(board[nx][ny] - board[cur[0]][cur[1]]);
                    tmpDis = tmpDis * tmpDis;

                    int next = dis[cur[0]][cur[1]] + tmpDis;

                    if(next > d)
                        continue;

                    if(dis[nx][ny] > next){
                        dis[nx][ny] = next;
                        q.add(new int[]{nx,ny,dis[nx][ny]});
                    }

                }else{

                    if(dis[cur[0]][cur[1]] + 1 > d)
                        continue;

                    if(dis[nx][ny] > dis[cur[0]][cur[1]] + 1) {
                        dis[nx][ny] = dis[cur[0]][cur[1]] + 1;
                        q.add(new int[]{nx,ny,dis[nx][ny]});
                    }
                }
            }
        }

        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++){
                tmpDis[i][j] += dis[i][j];
            }
        }
    }
}