[백준]JAVA - 20926번: 얼음 미로

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

20926번: 얼음 미로

풀이

포켓몬 얼음동굴이 생각나는 다익스트라 문제.

 

테라, 바위, 구멍, 출구가 char형이라서 int형으로 임의의 값을 줘서 int형 배열로 선언했다.

static int Rock = 100, Hole = -1, Escape = 200, W, H;
 
for (int i=0; i<H; i++) {
    String str = br.readLine();
    for (int j=0; j<W; j++) {
        int tmp = str.charAt(j);
                
        if (tmp == 'T') {
            sx = i;
            sy = j;
        }
        
        else if (tmp == 'R') map[i][j] = Rock;
        else if (tmp == 'H') map[i][j] = Hole;
        else if (tmp == 'E') map[i][j] = Escape;
        else map[i][j] = tmp - '0';
    }
}

 

아래 3가지 조건을 지켜주면서 bfs를 돌리면 된다.

1. 4방향으로 움직일 수 있고, 중간에 돌이 있다면 멈출 수 없다.
2. 범위를 벗어나거나 구멍에 빠지면 그대로 떨어진다.
3. 출구에 도착했을 경우 최단 거리를 비교한다.

while (true) {
    nx += dx[d];
    ny += dy[d];
                    
    if (nx < 0 || ny < 0 || nx >= H || ny >= W) break;
    if (map[nx][ny] == Hole) break;
    if (map[nx][ny] == Rock) {
        nx -= dx[d];
        ny -= dy[d];
                        
        pq.add(new Pos(nx, ny, sec));
        break;
    }
                    
    if (map[nx][ny] == Escape) {
        ans = Math.min(ans, sec);
        break;
    }
                    
    sec += map[nx][ny];
}

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int Rock = 100, Hole = -1, Escape = 200, W, H;
    static int ans = Integer.MAX_VALUE;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] map;
    
    public static class Pos implements Comparable<Pos> {
        int x, y, sec;
        
        public Pos (int x, int y, int sec) {
            this.x = x;
            this.y = y;
            this.sec = sec;
        }
        
        public int compareTo (Pos o) {
            return this.sec - o.sec;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        
        map = new int[H][W];
        int sx = 0, sy = 0;
        
        for (int i=0; i<H; i++) {
            String str = br.readLine();
            for (int j=0; j<W; j++) {
                int tmp = str.charAt(j);
                
                if (tmp == 'T') {
                    sx = i;
                    sy = j;
                }
                
                else if (tmp == 'R') map[i][j] = Rock;
                else if (tmp == 'H') map[i][j] = Hole;
                else if (tmp == 'E') map[i][j] = Escape;
                else map[i][j] = tmp - '0';
            }
        }
        
        bfs(sx, sy);
        if (ans == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);
    }
    
    public static void bfs(int x, int y) {
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        boolean[][] visited = new boolean[H][W];
        
        pq.add(new Pos(x, y, 0));
        
        while (!pq.isEmpty()) {
            Pos cur = pq.poll();
            
            if (visited[cur.x][cur.y]) continue;
            visited[cur.x][cur.y] = true;
            
            for (int d=0; d<4; d++) {
                int nx = cur.x;
                int ny = cur.y;
                int sec = cur.sec;
                
                while (true) {
                    nx += dx[d];
                    ny += dy[d];
                    
                    if (nx < 0 || ny < 0 || nx >= H || ny >= W) break;
                    if (map[nx][ny] == Hole) break;
                    if (map[nx][ny] == Rock) {
                        nx -= dx[d];
                        ny -= dy[d];
                        
                        pq.add(new Pos(nx, ny, sec));
                        break;
                    }
                    
                    if (map[nx][ny] == Escape) {
                        ans = Math.min(ans, sec);
                        break;
                    }
                    
                    sec += map[nx][ny];
                }
            }
        }
    }
}