[JAVA]백준 3055번: 탈출

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

3055번: 탈출

1. 문제 설명

 

고슴도치가 비버의 굴로 도망가 홍수를 피하려고 한다.

 

매 분마다 고슴도치와 물은 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다.

 

고슴도치는 물로 차 있는 곳과 돌을 통과할 수 없으며, 물도 돌을 통과할 수 없다.

 

고슴도치는 다음 시간에 물이 찰 예정인 칸으로도 이동할 수 없다.

 

숲의 지도가 주어질 때, 고슴도치가 안전하게 비버의 굴로 도망가기 위해 필요한 최소 시간을 구하여라.

 

고슴도치가 도망갈 수 없다면 "KAKTUS"를 출력한다.

 

2. 풀이

 

- int time : 현재 시간 (최소 이동 시간으로 사용 가능)

- Queue water : 물이 현재 시간에 차 있을 수 있는 위치

- Queue mouse : 고슴도치가 현재 시간에 있을 수 있는 위치

- char[][] map : 현재 시간에 숲의 상황

 

 

고슴도치가 다음 시간에 물이 찰 예정인 칸으로 이동할 수 없으므로 BFS를 이용하여 물을 먼저 이동시킨 후, 고슴도치를 이동시켜가며 비버의 굴로 이동이 가능한지 확인하면 된다.

 

물의 경우 이동하려고 하는 다음의 위치가 * (이미 물이 차 있는 곳), D( 비버의 굴), X(돌) 인 경우 이동할 수 없다.

 

고슴도치의 경우 이동하려고 하는 다음의 위치가 *(물이 차 있는 곳), X(돌), S(이미 고슴도치가 지나온 곳)인 경우 이동할 수 없다.

 

visited 배열을 선언해서 이미 지나온 곳들을 확인하지 않고, map[x][y]의 값을 이용해서 이미 지나온 곳인지 확인하였다. (고슴도치의 경우 -> S, 물의 경우 -> *)

 

고슴도치가 다음의 이동할 수 있는 위치가 D인 경우 최소 시간을 출력하고 종료한다.

 

고슴도치의 다음의 이동할 수 있는 위치가 D가 아닌 경우 map에 S를 저장하고, 물의 경우 다음의 이동할 수 있는 위치에 *을 저장한다.

 

만약, 고슴도치가 D에 도착하지 못하는 경우 "KAKTUS"를 출력하면 된다.

 

3. 코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static Queue<Dir> water = new LinkedList<>();
    public static Queue<Dir> mouse = new LinkedList<>();
    public static char[][] map;
    public static int[][] plus = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public static int R, C;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        // R,C 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int time = 0;
        boolean flag = false;

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());


        // 지도, 물, 고슴도치 위치 저장
        map = new char[R][C];

        for (int x = 0; x < R; x++) {

            String line = br.readLine();

            for (int y = 0; y < C; y++) {
                map[x][y] = line.charAt(y);

                if (map[x][y] == 'S') {
                    mouse.add(new Dir(x, y));
                }
                if (map[x][y] == '*') {
                    water.add(new Dir(x, y));
                }
            }

        }

        // move
        while (!mouse.isEmpty()) {
            int water_size = water.size();

            for (int x = 0; x < water_size; x++) {

                Dir now_water = water.poll();

                int now_x = now_water.x;
                int now_y = now_water.y;

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

                    int next_x = now_x + plus[y][0];
                    int next_y = now_y + plus[y][1];

                    if (isValid(true, next_x, next_y)) {
                        map[next_x][next_y] = '*';
                        water.add(new Dir(next_x, next_y));
                    }

                }

            }

            int mouse_size = mouse.size();

            for (int x = 0; x < mouse_size; x++) {
                Dir now_mouse = mouse.poll();

                int now_x = now_mouse.x;
                int now_y = now_mouse.y;



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

                    int next_x = now_x + plus[y][0];
                    int next_y = now_y + plus[y][1];

                    if (isValid(false, next_x, next_y)) {

                        if (map[next_x][next_y] == 'D') {
                            flag = true;
                            break;
                        }
                        map[next_x][next_y] = 'S';
                        mouse.add(new Dir(next_x, next_y));
                    }

                }

                if(flag)
                    break;
            }

            if(flag)
                break;

            time++;

        }

        if(flag)
            System.out.println(time+1);
        else
            System.out.println("KAKTUS");
    }

    // water -> true, mouse -> false
    public static boolean isValid(boolean sep,int x, int y) {


        // 범위 벗어남
        if (x < 0 || x >= R || y < 0 || y >= C) {
            return false;
        }

        // 돌
        if(map[x][y]=='X')
            return false;

        // 물은 비버의 굴을 갈 수 없다. 또한 이미 물이 차있으면 또 갈 필요가 없다.
        if (sep && (map[x][y]=='D' || map[x][y]=='*')) {
            return false;
        }

        // 고슴도치는 물이 차 있는 곳은 갈 수 없다. 이미 지나온 길이면 갈 필요 없다.
        if (!sep && (map[x][y] == '*' || map[x][y]=='S')) {
            return false;
        }

        return true;

    }


    public static class Dir{
        int x, y;

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

}