[백준]22255: 🦖호석사우루스 - JAVA

[백준]22255: 호석사우루스

22255번: 호석사우루스

풀이

🪑 시작 노드에서 도착 노드로 가는 최소 비용을 구하는 문제이다. (최단 거리 아님!) 한 정점에서 다른 정점으로 가는 최소비용! 다익스트라 문제이다.

 

📝 문제의 조건을 정리해 보자!'

• 3K번째 이동: 상 하 좌 우로 이동 가능하다.
• 3K + 1번째 이동: 상 하로 이동 가능하다.
• 3K + 2번째 이동: 좌 우로 이동 가능하다.
• 시작노드 ~ 도착노드로 가는 최소 비용을 구한다.

 

 

🔧 문제 풀이 과정은 다음과 같다.

1. 다익스트라 알고리즘을 사용하여 시작 노드에서 도착 노드로 가는 모든 최소 비용을 구한다.
2. 최소 비용이 존재 하면 해당 비용을, 존재 하지 않으면 -1을 출력한다.

 

🔹 다익스트라 알고리즘을 사용한다.

- 각 노드의 최소 비용을 저장해 주기 위한 dist배열을 3차원으로 만들어 주었다. 몇 번째 이동이냐에 따라 값이 달라질 수 있기 때문이다.

- 이동 번째에 따라 갈 수 있는 방향이 달라지므로 조건문을 사용하여 구별해 주었다.

- 현재 노드에서 이동하여 얻을 수 있는 비용이 다음으로 이동할 위치의 비용보다 작으면 갱신해 주었다.

 

🔹 최소 비용이 존재 하면 해당 비용을, 존재 하지 않으면 -1을 출력한다.

- 다익스트라 함수 리턴 타입은 최소 비용을 얻을 때의 이동 횟수이다.

- 이 이동 횟수가 -1이라면 최소 비용을 얻을 수 없으므로 -1을 출력하고, -1이 아니라면 해당 위치에서의 해당 이동 횟수일 때의 최소 비용을 출력해 준다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[][] board;
    static int[] dx = {-1, 1, 0, 0}; //상 하 좌 우 
    static int[] dy = {0, 0, -1, 1};
    static int[][][] dist;
    static PriorityQueue<Node> q;
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        //입력
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        str = bf.readLine();
        st = new StringTokenizer(str);
        int s_x = Integer.parseInt(st.nextToken()) - 1;
        int s_y = Integer.parseInt(st.nextToken()) - 1;
        int e_x = Integer.parseInt(st.nextToken()) - 1;
        int e_y = Integer.parseInt(st.nextToken()) - 1;
 
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            str = bf.readLine(); 
            st = new StringTokenizer(str);
            for(int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //입력 끝
 
        dist = new int[n][m][3];// 이동한 번째가 3k, 3k+1 3k+2에 따라 결과 달라짐
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int k = 0; k < 3; k++) {
                    dist[i][j][k] = Integer.MAX_VALUE;
                }
            }  
        }
 
        int result_count = dijkstra(s_x, s_y, e_x, e_y);
        if(result_count == -1) System.out.println("-1");
        else System.out.println(dist[e_x][e_y][result_count % 3]);
    }
 
    public static int dijkstra(int x, int y, int e_x, int e_y) {
        q = new PriorityQueue<>();
        q.offer(new Node(x, y, 1, 0));
        dist[x][y][1] = 0;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
 
            if(dist[current.x][current.y][current.count % 3] < current.cost) continue; //현재 경로보다 더 작은 경로 이미 존재
            if(current.x == e_x && current.y == e_y) return current.count;
            
            if(current.count % 3 == 0) {
                for(int i = 0; i < 4; i++) cal_dist(i, current);
            } else if(current.count % 3 == 1) {
                for(int i = 0; i < 2; i++) cal_dist(i, current);
            } else {
                for(int i = 2; i < 4; i++) cal_dist(i, current);
            }
        }
        return -1;
    }
 
    public static void cal_dist(int i, Node current) {
        int nx = current.x + dx[i];
        int ny = current.y + dy[i];
                    
        if(nx < 0 || ny < 0 || nx >= n || ny >= m) return ;
        if(board[nx][ny] == -1) return;
        if(dist[nx][ny][(current.count + 1) % 3] <= board[nx][ny] + current.cost) return;
        dist[nx][ny][(current.count + 1) % 3] = board[nx][ny] + current.cost;
        q.offer(new Node(nx, ny, current.count + 1, dist[nx][ny][(current.count + 1) % 3]));
    }
 
    public static class Node implements Comparable<Node>{
        int x, y, count, cost;
 
        public Node(int x, int y, int count, int cost) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}