백준 1486 자바 - 등산 (boj 1486 java)

문제 : boj1486

 

※ 블로그 만들기 이전에 깃헙에 텍스트로만 작성해둔 풀이라 그림도 없고 다른 글들과 말투가 다릅니다. 날잡고 옮겨야지 생각은 했는데 블로그 만들기 이전에 푼게 900개정도 이기도 하고, 요즘 푸는거 풀이 작성하기도 빡쌔므로 아무래도 전부 새로 작성해서 옮길 시간을 없을 것 같아서 틈틈히 그냥 깃헙에 적어둔 텍스트로만 된 풀이라도 옮겨둘 생각입니다.

 

  모든 위치에서 시작할 수 있는게 아니고, 딱 0,0 지점에서 출발이 가능하므로 결국 0,0에서 모든 지점으로의 거리와 모든 지점에서 0,0으로의 거리를 알면 solution 함수처럼 D 이내의 왔다가 다시 오는 거리 중 가장 높이가 높은걸 찾으면 됨.

  그럼 결국 위에서 말한 2가지만 구할 수 있으면 되는데, 플로이드 와샬로 한방에 구해도 되고, 다익스트라로 구해도 됨.
전자의 경우 N^3 이므로 (25*25)^3 으로 잘못하면 시간초과날거라고 생각되어 다익스트라로 해서 코드가 복잡해진거임. 실제로 후자로하니 100ms도 안걸렸음.

 

  다익스트라 사용 시, 어느 지점에서 다른 모든 지점으로의 거리는 쉽게 구할 수 있고, 그 반대(역방향)가 문제인데 사실 모든 간선을 reverse 해서 리버스 다익스트라를 돌리면 반대로 해당 지점으로의 거리를 구할 수 있음. (69line에서 리버스일 시 간선을 거꾸로 구함) 거기까지 알고 있으면 다익스트라만 짤 줄 알면 풀 수 있음.

 

 

 

코드 : github

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

class Node {
    int r, c, d;
    public Node(int r, int c, int d) {
        this.r = r;
        this.c = c;
        this.d = d;
    }
}

public class Main {
    private static StringTokenizer st;
    private static int r,c,t,d;
    private static int[][] map;
    private static int DIST_LIMIT = 52*52*25*25+1;

    private static int solution(int[][] a, int[][] b) {
        int max = 0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (a[i][j] + b[i][j] > d)  continue;
                max = Math.max(max, map[i][j]);
            }
        }
        return max;
    }

    private static int getGap(int a, int b) {
        if (Math.abs(a-b) > t) return -1;
        if (a >= b) return 1;
        return (b-a) * (b-a);
    }

    private static int[][] f(boolean reverse) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.d - o2.d;
            }
        });
        int[][] dist = new int[r][c];
        boolean[][] v = new boolean[r][c];

        for (int[] row : dist) Arrays.fill(row, DIST_LIMIT);
        pq.add(new Node(0, 0, 0));
        dist[0][0] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int cr = cur.r;
            int cc = cur.c;
            int cd = cur.d;

            if (v[cr][cc]) continue;
            v[cr][cc] = true;

            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (((dr^dc)&1) != 1) continue;
                    int nr = cr + dr;
                    int nc = cc + dc;
                    if (nr < 0 || nr >= r || nc < 0 || nc >= c) continue;
                    int gap = !reverse ? getGap(map[cr][cc], map[nr][nc]) : getGap(map[nr][nc], map[cr][cc]);
                    if (gap == -1 || dist[nr][nc] < cd+gap) continue;

                    dist[nr][nc] = cd+gap;
                    pq.add(new Node(nr, nc, dist[nr][nc]));
                }
            }
        }
        return dist;
    }

    private static int ni() { return Integer.parseInt(st.nextToken()); }

    private static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        r=ni(); c=ni(); t=ni(); d=ni();
        map = new int[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                char tmp = row.charAt(j);
                map[i][j] = tmp >= 'a' ? tmp - 'a' + 26 : tmp - 'A';
            }
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        int answer = solution(f(false), f(true));
        System.out.println(answer);
    }
}