[JAVA] 백준 3055 : 탈출

[JAVA] 백준 3055 : 탈출

문제

시간이 지날 수록 물이 차오르는 상황에서 고슴도치 집에서 출발한 고슴도치가 친구인 비버 집에 얼마만에 도착할 수 있는가를 구하는 문제. R행 C열로 이뤄진 지도에는 빈칸(.), 물(*), 돌(X), 비버집(D), 고슴도치집(S)이 주어져있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있고, 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다. 이러한 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 문제.

접근방법

1. 맵의 입력을 숫자로 변환하여 받는다.

   • 빈칸(-2), 물(-1), 돌(2) 고슴도치집(0), 비버집(-100)으로 설정하였다. → 처음 큐에 들어가면서 1씩 증가해야 하므로 고슴도치 집을 0으로 설정하였고, 이와 구분해주기 위해 다른 값들은 위와 같이 설정하였다.

2. 입력을 받으면서 물을 큐에 넣고, 그 뒤에 고슴도치의 위치를 큐에 넣으면서 BFS를 수행한다. 먼저 물과 인접한 빈칸이 물로 바뀌고, 고슴도치는 나머지 빈칸을 이동해 비버의 집까지의 이동거리를 체크한다.

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
​
public class Main{
​
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
​
    static class Pos{
        int r;
        int c;
        public Pos(int r, int c) {this.r = r; this.c = c;}
    }
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
​
        Queue<Pos> queue = new LinkedList<>();
        int map[][] = new int[N+2][M+2];
        boolean check_doch[][] = new boolean[N+2][M+2];
        boolean check_rain[][] = new boolean[N+2][M+2];
​
        // 돌(테두리) 세우기
        for(int i=0; i<N+2; i++)
            for(int j=0; j<M+2; j++)
                map[i][j] = 2;  //  1-벽(돌)
​
        Pos dochi = new Pos(0,0);
        Pos bibber = new Pos(0,0);
        for(int i=1; i<=N; i++){
            String line = sc.next();
            for(int j=1; j<=M; j++){
                char input = line.charAt(j-1);
                switch (input){
                    case '*':   // 물
                        map[i][j] = -1;
                        queue.offer(new Pos(i, j));
                        check_rain[i][j] = true;
                        break;
                    case 'S':   // 고슴도치 집
                        map[i][j] = 0;
                        dochi = new Pos(i, j);
                        break;
                    case '.':   // 빈칸
                        map[i][j] = -2;
                        break;
                    case 'D':   // 비버 집
                        map[i][j] = -100;
                        bibber = new Pos(i, j);
                        break;
                    case 'X':   // 돌
                        map[i][j] = 2;
                        break;
                }
            }
        }
        queue.offer(dochi);
        check_doch[dochi.r][dochi.c] = true;
​
        First_Loop:
        while(!queue.isEmpty()) {
            Pos cur_pos = queue.poll();
            for (int i = 0; i < 4; i++) {
                Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
​
                // 현재 칸이 빗물일 경우 -> 빗물 증가 (방문여부 확인할 필요x)
                if (map[cur_pos.r][cur_pos.c] == -1) {
                    // 주변 칸이 빈칸(-2)일 경우 큐에 넣는다.
                    if (map[next_pos.r][next_pos.c] == -2) {
                        map[next_pos.r][next_pos.c] = -1;
                        check_rain[next_pos.r][next_pos.c] = true;
                        queue.offer(next_pos);
                    }
                } // 현재 칸이 빈칸일 경우 -> 고슴도치 이동거리 증가
                else {
                    // 주변 칸이 방문하지 않았으면서
                    if (!check_doch[next_pos.r][next_pos.c]) {
                        // 비버의 집(-100)일 경우 while문 탈출
                        if (map[next_pos.r][next_pos.c] == -100){
                            map[next_pos.r][next_pos.c] = map[cur_pos.r][cur_pos.c] + 1;
                            break First_Loop;
                        }// 빈칸(-2)일 경우 계속해서 이동
                        else if(map[next_pos.r][next_pos.c] == -2){
                            map[next_pos.r][next_pos.c] = map[cur_pos.r][cur_pos.c] + 1;
                            check_doch[next_pos.r][next_pos.c] = true;
                            queue.offer(next_pos);
                        }
                    }
                }
            }
        }
​
        if(map[bibber.r][bibber.c] == -100)
            System.out.println("KAKTUS");
        else
            System.out.println(map[bibber.r][bibber.c]);
    }
}