녹색 옷 입은 애가 젤다지? (골드5, 백준 4485번 문제)

Question: 녹색 옷 입은 애가 젤다지?

녹색 옷 입은 애가 젤다지? (백준 4485번 문제)

Simple Explanation of Dijkstra

YouTube Video

Sample input

3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

Sample output

Problem 1: 20
Problem 2: 19
Problem 3: 36

Solution

• you can use a priority queue but you don't have to.

import java.util.*;

public class Main {
    // Without a priority queue
    // Directions for moving in the grid: up, down, left, right
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int problemCount = 1;
        
        while (true) {
            int N = sc.nextInt();
            if (N == 0) break;  // End of input
            
            int[][] cave = new int[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cave[i][j] = sc.nextInt();
                }
            }

            // Run Dijkstra's algorithm and get the minimum cost
            int result = dijkstra(cave, N);

            // Print the result for the current problem
            System.out.println("Problem " + problemCount + ": " + result);
            problemCount++;
        }
    }

    // Dijkstra's algorithm to find the minimum cost to reach the bottom-right corner
    public static int dijkstra(int[][] cave, int N) {
        // Distance array to store the minimum cost to reach each cell
        int[][] dist = new int[N][N];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        // Priority queue to process cells in order of increasing cost
        Queue<int[]> pq = new LinkedList<>();
        // Queue<Integer> q = new Queue<Integer>();

        
        // Starting point: top-left corner (0, 0)
        dist[0][0] = cave[0][0];
        pq.add(new int[] { 0, 0, cave[0][0] }); // x, y, cost
        
        // Process the priority queue
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int x = current[0];
            int y = current[1];
            int cost = current[2];
            
            // If we've already found a shorter path to this cell, skip it
            if (cost > dist[x][y]) 
                continue;
            
            // Explore the 4 neighbors
            for (int i = 0; i < 4; i++) {
                // neighbor's x,y coordinate
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                // Check if the neighbor is within bounds
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    int newCost = cost + cave[nx][ny];
                    
                    // If a cheaper path to the neighbor is found, update the distance and add to the queue
                    // If not no point checking the neigbor because it would have been already chekced
                    if (newCost < dist[nx][ny]) { // don't worry! all nodes will be added at least once because they are initized as Integer.MAX_VALUE
                        dist[nx][ny] = newCost; // smaller updated node can change the minimum distance of the surrounding nodes
                        pq.add(new int[] { nx, ny, newCost });
                    }
                }
            }
        }
        
        // Return the minimum cost to reach the bottom-right corner
        return dist[N - 1][N - 1];
    }
}