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

Problem 💻

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

 

링크가 ‘도둑루피’로 가득찬 동굴에서 (0, 0) → (n-1, n-1)까지 최소한의 루피를 잃으면서 도착해야 하는 문제이다. 동굴의 각 칸마다 도둑루피의 가치가 주어지고 해당 가치가 클수록 잃는 돈이 많아지는 것이다.

---

 

Approach 1 ⭕

• 다익스트라 (00:13:12)

 

이 문제의 해결방법은 ‘도둑루피’를 조금 다르게 생각해 해당 노드로 가는 ‘가중치’라고 생각하는 것이다. 해당 노드로 가는 모든 간선의 가중치가 도둑루피의 가치로 고정되는 것이다. 그럼, 가중치 그래프의 최단 거리를 구하기 위해서 사용할 수 있는 알고리즘인 ‘다익스트라’를 생각할 수 있다.

---

 

Approach 2 ⭕

• BFS (00:10:27)

 

두 번째로는 BFS를 이용한 방법이 있다. 각 칸에 도달했을 때 도둑루피의 합이 현재 칸에 저장된 합보다 작다면 해당 합으로 갱신하면서 최소 도둑루피를 구하는 방법이다.

2
5 5
3 9

이러한 동굴이 있을 때 처음에 (0, 0) → (0, 1) → (1, 1)로 가면 24의 루피를 잃게되지만 (0, 0) → (1, 0) → (1, 1) 경로로 가게 되면 17만큼의 루피를 잃게되므로 이를 갱신시켜주는 것이다.

 

만약 반대로 (0, 0) → (1, 0) → (1, 1) 경로로 먼저 갔다가 (0, 0) → (0, 1) → (1, 1) 경로로 온다면 갱신하지 않고 차례를 넘긴다.

 

이처럼 visited 배열을 원래 bfs처럼 그 칸을 가기까지의 최단 거리로 보지않고 그 칸을 가기까지의 최소 도둑루피 가치로 보고 문제를 푸는 것이다.

---

 

Solution 💡

// 다익스트라
public class BOJ_4485 {

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

    private static int[][] dungeon;
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = 1;
        while ((n = Integer.parseInt(br.readLine())) != 0) {
            dungeon = new int[n][n];

            for (int y = 0; y < n; y++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int x = 0; x < n; x++) dungeon[y][x] = Integer.parseInt(st.nextToken());
            }

            int[][] shortest = dijkstra(0, 0);
            System.out.println("Problem " + t++ + ": " + shortest[n-1][n-1]);
        }
    }

    public static int[][] dijkstra(int y, int x) {
        int[][] shortest = new int[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(shortest[i], 987654321);
        shortest[y][x] = dungeon[y][x];

        boolean[][] visited = new boolean[n][n];

        while (true) {
            int smallY = 0;
            int smallX = 0;
            int value = Integer.MAX_VALUE;
            for (int yy = 0; yy < n; yy++) {
                for (int xx = 0; xx < n; xx++) {
                    if (!visited[yy][xx] && value > shortest[yy][xx]) {
                        value = shortest[yy][xx];
                        smallY = yy;
                        smallX = xx;
                    }
                }
            }

            if (smallY == n-1 && smallX == n-1) break;
            visited[smallY][smallX] = true;

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

                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                if (visited[ny][nx]) continue;

                shortest[ny][nx] = Math.min(shortest[smallY][smallX] + dungeon[ny][nx], shortest[ny][nx]);
            }
        }

        return shortest;
    }
}

// BFS
public class BOJ_4485_2 {

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

    private static int[][] dungeon;
    private static int[][] visited;
    private static int n;

    private static class Point {
        int y, x;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = 1;
        while ((n = Integer.parseInt(br.readLine())) != 0) {
            dungeon = new int[n][n];
            visited = new int[n][n];
            for (int i = 0; i < n; i++) Arrays.fill(visited[i], 987654321);

            for (int y = 0; y < n; y++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int x = 0; x < n; x++) dungeon[y][x] = Integer.parseInt(st.nextToken());
            }

            bfs(0, 0);
            System.out.printf("Problem %d: %d\\n", t++, visited[n-1][n-1]);
        }
    }

    private static void bfs(int y, int x) {
        ArrayDeque<Point> q = new ArrayDeque<>();
        q.add(new Point(y, x));

        visited[y][x] = dungeon[y][x];
        while (!q.isEmpty()) {
            Point p = q.poll();

            for (int i = 0; i < 4; i++) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];

                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                if (visited[ny][nx] <= visited[p.y][p.x] + dungeon[ny][nx]) continue;

                visited[ny][nx] = visited[p.y][p.x] + dungeon[ny][nx];
                q.add(new Point(ny, nx));
            }
        }
    }
}