[백준] 1486번 : 등산

1486번: 등산

---

[Dijkstra / Floyd Warshall]

모든 정점에서 다른 모든 정점에 대한 최단 경로를 구하는 문제이므로 다익스트라를 이용하거나, 플로이드 와샬을 이용해도 무방할 듯 하다. 나는 N x M개의 모든 정점에 대해 다익스트라 알고리즘을 수행하였다.

 

우선 map이 알파벳으로 주어지는데, 각 알파벳은 그에 맞는 높이를 정수형으로 가진다. 따라서 map을 저장할 때 char가 아닌 int로 변환해서 저장하였다.

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++){
                char ch = str[j-1];

                if(ch >= 'A' && ch <= 'Z') map[i][j] = ch - 65;
                else if(ch >= 'a' && ch <= 'z') map[i][j] = ch - 71;

            }
        }

 

그리고 모든 정점(i, j)는 다른 모든 정점들에 대하여 최단 경로를 갖을 수 있으므로 4차원 배열  dist[ ][ ][ ][ ]를 준비한다.

static int[][] map = new int[26][26], dist[][] = new int[26][26][26][26];

/* ... */
//dist 초기화

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                for(int k=1; k<=r; k++)
                    for(int z=1; z<=c; z++)
                        dist[i][j][k][z] = INF;

 

다음은 Point라는 클래스를 지정하는데, Point는 y좌표, x좌표 그리고 time을 멤버 변수로 갖는다. 우선 순위 큐를 사용할 것 이므로 Comparable을 구현한다.

    static class Point implements Comparable<Point>{
        int y, x, time;
        public Point(int yy, int xx, int t){
            y=yy;
            x=xx;
            time=t;
        }
        @Override
        public int compareTo(Point o) {
            return time - o.time;
        }
    }

 

이제 이 문제의 핵심인 다익스트라 메서드를 만들어준다. 인자로는 시작할 정점의 y좌표, x좌표를 받는다.

    static void Dijkstra(int yy, int xx){

        Queue<Point> Q = new PriorityQueue<>();
        
        dist[yy][xx][yy][xx] = 0;
        Q.add(new Point(yy, xx, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int time = p.time;

            if(dist[y][x][yy][xx] < time) continue;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nTime;

                if(ny < 1 || nx < 1 || ny > r || nx > c) continue; //맵의 범위를 벗어나면
                if(Math.abs(map[y][x] - map[ny][nx]) > t) continue; //각 정점의 높이 차가 t보다 크면 Skip

                if(map[ny][nx] <= map[y][x]) //현재 정점의 높이가 다음 정점의 높이보다 크거나 같음
                    nTime = time + 1;
                else //현재 정점의 높이가 다음 정점의 높이보다 작음
                    nTime = (int) Math.pow((map[ny][nx] - map[y][x]), 2) + time;

                if(dist[ny][nx][yy][xx] > nTime && nTime <= d){
                    dist[ny][nx][yy][xx] = nTime;
                    Q.add(new Point(ny, nx, nTime));
                }
            }
        }
    }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point implements Comparable<Point>{
        int y, x, time;
        public Point(int yy, int xx, int t){
            y=yy;
            x=xx;
            time=t;
        }
        @Override
        public int compareTo(Point o) {
            return time - o.time;
        }
    }
    static final int INF = 1000000000;
    static int[][] map = new int[26][26], dist[][] = new int[26][26][26][26];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static int r, c, t, d;

    static void Dijkstra(int yy, int xx){

        Queue<Point> Q = new PriorityQueue<>();
        dist[yy][xx][yy][xx] = 0;
        Q.add(new Point(yy, xx, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            
            int y = p.y;
            int x = p.x;
            int time = p.time;

            if(dist[y][x][yy][xx] < time) continue;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nTime;

                if(ny < 1 || nx < 1 || ny > r || nx > c) continue;
                if(Math.abs(map[y][x] - map[ny][nx]) > t) continue;

                if(map[ny][nx] <= map[y][x])
                    nTime = time + 1;
                else
                    nTime = (int) Math.pow((map[ny][nx] - map[y][x]), 2) + time;

                if(dist[ny][nx][yy][xx] > nTime && nTime <= d){
                    dist[ny][nx][yy][xx] = nTime;
                    Q.add(new Point(ny, nx, nTime));
                }
            }
        }
    }

    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());
        t = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                for(int k=1; k<=r; k++)
                    for(int z=1; z<=c; z++)
                        dist[i][j][k][z] = INF;

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++){
                char ch = str[j-1];

                if(ch >= 'A' && ch <= 'Z') map[i][j] = ch - 65;
                else if(ch >= 'a' && ch <= 'z') map[i][j] = ch - 71;

            }
        }

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                Dijkstra(i, j);

        int max = 0;

        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                if(dist[i][j][1][1] + dist[1][1][i][j] <= d)
                    max = Math.max(max, map[i][j]);

        System.out.println(max);

    }
}