백준 20926 (얼음 미로) - java

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

20926번: 얼음 미로

 

문제

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

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

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

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

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

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

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

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

 

유형 : 구현 + BFS

 

접근 방식

• 구슬 탈출과 비슷한 로직으로 수행된다.
  • 벽에 부딛힌 경우에만 다음 지점으로 이동할 수 있기 때문에 하나의 좌표를 기준으로 4방위로 벽에 다다를 때까지 이동시킨다.
• 방문 배열에 대해
  • 위 문제에서 방문 배열을 어떻게 체크할 것인지가 중요한다. 결과부터 얘기하자면 움직임을 종료한 위치를 기준으로 방문 체크한다.
  • 벽에 부딛힌 경우 다음 좌표로 이동하기 때문에 해당 지점을 이미 방문했는지 체크하는 것이다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int sx,sy;

    static char[][] board;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0}; // 4방위 탐색

    static int result = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        board = new char[n+1][m+1];

        for(int i=1;i<=n;i++){
            String line = bf.readLine();

            for(int j=1;j<=m;j++){
                board[i][j] = line.charAt(j-1);

                if(board[i][j] == 'T'){
                    sx = i;
                    sy = j; // 시작 지점
                } 
            }
        }

        search();
        System.out.println(result);

        bf.close();
    }

    static void search(){
        int[][] v = new int[n+1][m+1]; // 거리 배열
        boolean[][] visit = new boolean[n+1][m+1]; // 방문 배열


        Queue<Node> q = new LinkedList<>();
        visit[sx][sy] = true;
        q.add(new Node(sx,sy));

        while (!q.isEmpty()) {
            Node cur = q.poll();

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

                while(true){
                    int nx = cur.x + (idx * dx[i]);
                    int ny = cur.y + (idx * dy[i]);

                    if(isOut(nx,ny))
                        break;

                    if(board[nx][ny] == 'H' || board[nx][ny] =='T') // 구멍에 빠지거나 시작 위치일 경우
                        break;

                    // 출구를 발견한 경우
                    if(board[nx][ny] == 'E'){

                        if(result == -1){
                            result =  v[cur.x][cur.y] + tmp;
                        }

                        else{
                            result = Math.min(result,v[cur.x][cur.y] + tmp);
                        }
                    }

                    // 벽에 다다른 경우 
                    if(board[nx][ny] == 'R'){
                        nx -= dx[i];
                        ny -= dy[i];

                        if(!visit[nx][ny] || v[nx][ny] > v[cur.x][cur.y] + tmp){
                            visit[nx][ny] = true;
                            v[nx][ny] = v[cur.x][cur.y] + tmp;
                            q.add(new Node(nx,ny));
                        }
                        break;
                    }

                    tmp += board[nx][ny] - '0'; // 미끌 시간 계산
                    idx++;
                }
            }
        }

    }

    static boolean isOut(int x,int y){
        if(x < 1 || x > n || y < 1 || y > m)
            return true;

        return false;
    }
}
class Node{
    int x;
    int y;

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