[알고리즘] 백준 > #4485. 녹색 옷 입은 애가 젤다지?

문제링크

백준 #4485. 녹색 옷 입은 애가 젤다지?

풀이방법

개인적으로 재미있는 문제였다! 아래, 왼쪽으로만 움직이는 게 아니니까 DP는 쓸 수 없었다. 완전탐색으로 풀어야하나.. 생각했었다. (0, 0) 부터 (n - 1, n - 1)까지의 최소 거리라고 생각해봤다. 그러니까 다익스트라가 생각났다! 각 위치를 하나의 노드로 보는 것이다. 그리고 주변(위, 아래, 오른쪽, 왼쪽)으로 이어진 간선이 있는 것이다. 이 부분에 dy, dx를 활용한거 빼고는 일반적인 다익스트라와 동일했다!

코드

class Solution4485 {
    int n;
    int[][] map;

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

    Solution4485(int n, int[][] map) {
        this.n = n;
        this.map = map;
    }

    int getMinCost() {
        int[][] costs = new int[n][n];
        for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) costs[y][x] = 200000;
        costs[0][0] = map[0][0];
        boolean[][] visited = new boolean[n][n];
        PriorityQueue<RupeePosition> q = new PriorityQueue<>(Comparator.comparingInt((RupeePosition a) -> costs[a.y][a.x]));
        q.offer(new RupeePosition(0, 0));

        while (!q.isEmpty()) {
            RupeePosition head = q.poll();

            if (visited[head.y][head.x]) continue;
            else visited[head.y][head.x] = true;

            if (head.x == (n - 1) && head.y == (n - 1)) break;

            for (int i = 0; i < 4; i++) {
                int nextY = head.y + dy[i];
                int nextX = head.x + dx[i];

                if (isInRange(nextY, nextX) && !visited[nextY][nextX]) {
                    int cost = costs[head.y][head.x] + map[nextY][nextX];
                    if (cost < costs[nextY][nextX]) {
                        costs[nextY][nextX] = cost;
                        q.offer(new RupeePosition(nextY, nextX));
                    }
                }
            }
        }

        return costs[n - 1][n - 1];
    }

    private boolean isInRange(int y, int x) {
        return ((y >= 0) && (y < n) && (x >= 0) && (x < n));
    }
}

class RupeePosition {
    int y;
    int x;

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