[백준] 20926번 - 얼음 미로 (Java)

문제

https://www.acmicpc.net/problem/20926

20926번: 얼음 미로

 

입력

 

출력

---

알고리즘

다익스트라, 구현

 

최단 시간을 물어봤으므로 그냥 BFS를 쓰면 되는거 아닌가라고 생각할 수 있지만, 각 칸에 가중치가 존재하므로 이 문제는 BFS로 풀 수 없다. 모든 가중치가 양수이므로 다익스트라로 최단 경로를 구하면 된다.

 

일반 다익스트라랑 똑같이, 2차원 배열의 다익스트라 구현 문제라고 생각하면 된다. 풀이 과정은 아래와 같다.

 

1. 그래프 탐색하는 것 처럼 방향벡터를 이용해서 위,아래,오른쪽,왼쪽 4방향을 다 탐색한다.

2. 그 방향으로 몇칸 미끄러질 수 있는지 확인한다. 만약에, 범위에 벗어나는 경우나 구덩이에 빠지는 경우는 제외한다. 또한, 출구에 도달하는 경우는 그 칸까지 이동 칸 수에 포함시켜준다.

3. 그 방향으로 미끄러진 칸 수 만큼 반복해서 움직이는데 걸린 시간을 구한다.

4. 다익스트라 알고리즘을 통해 거리를 비교해서 조건에 따라 갱신해주고 큐에 집어넣는다.

5. 1~4번 과정을 큐가 비워질때까지 반복한다.

6. 출구 칸에서의 기록된 최단 경로를 출력한다. 만약 최댓값에서 갱신이 안되어 있다면 -1을 출력한다.

 

구현이다보니 위 과정을 염두해두고 하나하나 따라가면서 코드를 읽어보면 이해가 갈 것이다.

---

코드

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

public class Main {
    public static class Node implements Comparable<Node>{
        int x,y,d;

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

        @Override
        public int compareTo(Node o) {
            return this.d - o.d;
        }
    }
    static int n,m;
    static char[][] board;
    static boolean[][] visited;
    static int[][] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new char[m][n];
        dist = new int[m][n];
        visited = new boolean[m][n];
        
        //다익스트라를 위한 최댓값 개잇ㄴ
        for(int i = 0; i<m; i++){
            Arrays.fill(dist[i], 500*500*9);
        }
        
        //초기 및 도착 위치
        int start_x = -1, start_y = -1, end_x = -1, end_y = -1;

        for(int i = 0; i<m; i++){
            String tmp = br.readLine();
            for(int j = 0; j<n; j++){
                char cur = tmp.charAt(j);
                board[i][j] = cur;
                if(cur == 'T'){
                    start_x = i;
                    start_y = j;
                }
                else if(cur == 'E'){
                    end_x = i;
                    end_y = j;
                }
            }
        }

        dijkstra(start_x, start_y);
        System.out.println(dist[end_x][end_y] == 500*500*9 ? -1 : dist[end_x][end_y]);
    }

    public static void dijkstra(int start_x, int start_y){
        int[] dirx = {1,-1,0,0};
        int[] diry = {0,0,1,-1};

        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start_x,start_y,0));
        dist[start_x][start_y] = 0;
        
        //2차원 다익스트라
        while(!queue.isEmpty()){
            Node cur = queue.poll();

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

            for(int i = 0; i<4; i++){
                //미끄러져서 범위에 벗어나지 않고 도달할 수 있는지 확인
                int check = slide(cur.x,cur.y, dirx[i], diry[i]);
                //미끄러졌을때 구멍에 빠지거나 범위에 벗어나는 경우
                if(check == -1) continue;

                int distance = 0;
                
                //미끄러지면서 이동한 거리 계산
                //1부터 시작하는 이유는 미끄러질때 현재 자리는 포함하지 않기 때문
                for(int j = 1; j< check+1; j++){
                    //E는 출구이므로 이는 거리 계싼에 포함시키지 않음
                    if(board[cur.x + j*dirx[i]][cur.y + j*diry[i]] == 'E') break;
                    distance += (board[cur.x + j*dirx[i]][cur.y + j*diry[i]] - '0');
                }
                
                //미끄러져서 최종적으로 도달한 좌표 (nx, ny)
                int nx = cur.x + check*dirx[i];
                int ny = cur.y + check*diry[i];
                //다익스트라를 통한 거리 갱신
                if(!visited[nx][ny] && dist[nx][ny] > dist[cur.x][cur.y] + distance){
                    dist[nx][ny] = dist[cur.x][cur.y] + distance;
                    //출구일 경우에는 큐에 넣어주면 안됨
                    if(board[nx][ny] != 'E') queue.add(new Node(nx, ny, dist[nx][ny]));
                }

            }
        }
    }
    
    //미끄러져서 범위에 벗어나는지 확인
    //범위에 벗어나지 않는다면 몇칸 미끄러졌는지 반환한다.
    public static int slide(int x, int y, int dirx, int diry){
        int count = 1;
        while(true){
            int nx = x + dirx*count;
            int ny = y + diry*count;
            
            //범위에 벗어나거나 구멍에 떨어지는 경우
            if(nx<0 || ny<0 || nx>=m || ny>=n || board[nx][ny] == 'H'){
                count = -1;
                break;
            }
            //돌에 도달하면 돌보다 한칸 뒤 만큼 이동했음을 반환
            if(board[nx][ny] == 'R'){
                count -= 1;
                break;
            }
            //출구면 출구있는 칸 까지는 이동해야됨
            if(board[nx][ny] == 'E') break;
            //한칸 이동
            count ++;
        }
        
        //-1이면 범위 벗어나는거임
        return count;
    }
}