[BOJ] 20926 : 얼음 미로 [G2]

 

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

 

 

 

 

문제

 

탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 멈출 수 없고 왼쪽 바위에 부딪힐 때까지 미끄러진다. 얼음 미로 바깥은 절벽이기 때문에 빠지면 탈출할 수 없다.

얼음 미로에는 4$4$가지 오브젝트가 있다.

1.   테라 : 얼음 미로에 갇힌 탐험가. 상하좌우 4$4$방향으로 이동할 수 있다. 얼음 미로에 단 1$1$명의 테라만 존재한다. 테라가 최초 위치한 빙판의 미끌 시간은 0$0$이다.
2.   바위 : 통과할 수 없다. 미끄러지다 부딪히면 앞에서 멈춘다.
3.   구멍 : 이곳에 빠지면 영영 탈출할 수 없다.
4.   출구 : 이곳에 방문하는 즉시 얼음 미로를 탈출한다. 얼음 미로에 단 1$1$개의 출구만 존재한다.

어떤 빙판 위에서 미끄러지는 데 걸리는 시간을 미끌 시간이라고 하자. 각 빙판마다 미끌 시간은 다를 수 있다.

테라가 어느 한쪽 방향으로 이동할 때, 테라가 미끄러지는 동안 위치한 빙판의 미끌 시간을 더하면 이동 시간을 구할 수 있다. 단, 이동 시간 계산과 관련하여 두 가지 규칙이 있다.

 

• 테라가 어느 한쪽 방향으로 이동을 시작할 때, 시작 빙판의 미끌 시간은 포함하지 않는다.
• 테라가 출구로 들어갈 때, 출구 빙판의 미끌 시간은 포함하지 않는다.

위 그림에서 테라가 위로 이동할 때의 이동 시간을 계산하자. 테라가 현재 서 있는, 시작 빙판의 미끌 시간 4$4$와 출구 빙판의 미끌 시간 0$0$을 제외하면 1+2=3$1 + 2 = 3$ 만큼의 시간이 걸린 뒤 출구를 통해 탈출함을 알 수 있다.

저체온증이 시작된 테라는 얼음 미로를 가능한 한 빨리 탈출하고 싶다. 얼음 미로를 탈출하는 데 걸리는 최단 시간을 계산하자.

 

입력

 

첫 번째 줄에는 얼음 미로의 가로 크기를 나타내는 정수 𝑊$W$(2≤𝑊≤500$2 \le W \le 500$), 세로 크기를 나타내는 정수 𝐻$H$(2≤𝐻≤500$2 \le H \le 500$)가 주어진다.

두 번째 줄부터 𝐻$H$개의 줄에 걸쳐 얼음 미로에 대한 정보가 주어진다.

테라는 T, 바위는 R, 구멍은 H, 출구는 E로 나타낸다.

빙판의 미끌 시간 𝑡$t$는 0$0$ 이상 9$9$ 이하의 정수로 나타낸다.

 

출력

얼음 미로를 탈출할 수 있다면 최단 탈출 시간을 출력한다.

얼음 미로를 탈출할 수 없다면 -1을 출력한다.

 

[예제 입력 1]

5 5
2E115
32411
11313
R42TH
124R6

[예제 출력 1]

9

 

 

 

[내 풀이]

우선순위 큐를 이용한 다익스트라 + 비트마스킹을 이용해 풀었습니다.

바위를 만났을 때만 cur.dir = 15를 넣어주어 (1111) 4방향 탐색이 가능하도록 하고,

바위를 만나지 않았을 경우는 진행방향으로만 탐색이 가능하도록 isVisited배열을 비트마스킹을 이용해 표현하였습니다.

 

 

 [내 코드]

import java.util.*;
import java.io.*;

public class BJ_20926 {

    static class Tera implements Comparable<Tera>{
        int r, c, t, dir;

        public Tera(int r, int c, int t, int dir) {
            this.r = r;
            this.c = c;
            this.t = t;
            this.dir = dir;
        }

        // 시간 기준 오름차순 정렬
        @Override
        public int compareTo(Tera o) {
            return Integer.compare(this.t, o.t);
        }
    }

    static int W, H;
    static char[][] map;
    static int[][] dxdy = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static PriorityQueue<Tera> pq;

    static int bfs() {

        int[][] isVisited = new int[H][W];

        while (!pq.isEmpty()) {
            Tera cur = pq.poll();

            for (int i = 0; i < 4; i++) {

		// 이동가능한 방향인지 검사
                if ((cur.dir & (1 << i)) == 0) continue;

                int dx = cur.r + dxdy[i][0];
                int dy = cur.c + dxdy[i][1];

                if (!isIn(dx, dy) || (isVisited[dx][dy] & (1<<i)) != 0) continue;

                isVisited[dx][dy] += 1<<i; // 방문 처리
                
                // 출구 만났을 때 => 정답
                if (map[dx][dy] == 'E') {
                    return cur.t;
                }

                // 바위 만났을 때 => 다시 4방 탐색 가능
                else if (map[dx][dy] == 'R') {
                    pq.offer(new Tera(dx - dxdy[i][0], dy - dxdy[i][1], cur.t, 15));
                    break;
                }

                // 구멍 만났을 때
                else if (map[dx][dy] == 'H') continue;

                // 일반 지형이면 이동시간 증가
                pq.offer(new Tera(dx, dy, cur.t + map[dx][dy] - 48, 1<<i));

            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception{
        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 char[H][W];
        pq = new PriorityQueue<>();
        for (int i = 0; i < H; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < W; j++) {
                if (map[i][j] == 'T') {
                    pq.offer(new Tera(i, j, 0, 15));
                }
            }
        }
        System.out.println(bfs());

    }

    // debug
    static void printMap(char[][] map) {
        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static boolean isIn(int x, int y) {
        return x>=0 && x<H && y>=0 && y<W;
    }
}

 

 

[회고]

* 유의할 점*
Tera implements Comparable<Tera> : O
Tera implements Comparator<Tera> : X

 

클래스에 정렬 우선순위를 지정해 줄 때는 'Comparable'을 사용해야 한다!

Comparator를 사용하려고 하면 아래와 같이 사용해야 한다.

static class Tera {
        int r, c, t, dir;

        public Tera(int r, int c, int t, int dir) {
            this.r = r;
            this.c = c;
            this.t = t;
            this.dir = dir;
        }
    }
    
    
==== 중략 =====

pq = new PriorityQueue<>(new Comparator<Tera>() {
            @Override
            public int compare(Tera o1, Tera o2) {
                return Integer.compare(o1.t, o2.t);
            }
        });