[실전 문제] SLIKAR

1. 문제

사악한 암흑의 군주 임정택은 드디어 원하던 마법 구슬을 손에 넣었고, 알랩숲에 홍수를 일으켰다! 이 숲에 살고 있는 고슴도치는 지금 당장 비버의 굴로 가능한 빨리 돌아가 홍수를 피하려고 한다.

 

알랩숲의 지도는 R행 C열로 구성되어 있다. 비어있는 곳은 '.'로 나타나 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표현되어 있다. 추가적으로, 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 표시되어 있다.

 

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물은 매 분마다 물이 있는 칸과 적어도 한 변을 공유하는 비어있는 모든 칸에 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물은 비버의 소굴로 이동할 수 없다.

 

알랩숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 도달하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

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

---

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

 

다음 R개 줄에 걸쳐 C개의 문자가 주어진다.('.', '*', 'X', 'D' or 'S') 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 도달할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없을 경우, "KAKTUS"를 출력한다.

예제 입력

case 1)

3 3
D.*
...
.S.

 

case 2)

3 3
D.*
...
..S

 

case 3)

3 6
D...*.
.X.X..
....S.

 

case 4)

5 4
.D.*
....
..X.
S.*.
....

예제 출력

case 1) 3

case 2) KAKTUS

case 3) 6

case 4) 4

 

 

 

2. 풀이

이 문제는 고슴도치와 물 각각을 모두 BFS로 처리하면 된다. 단, 주의해야할 점은 물은 반드시 인접한 곳만 물로 채워진다는 점이다.

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

public class Main {

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

    private static int n;
    private static int m;

    private static char[][] arr;

    private static int[] dy = {1, -1, 0, 0};
    private static int[] dx = {0, 0, 1, -1};

    private static Queue<int[]> hedgehog;
    private static Queue<int[]> water;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new char[n][m];

        hedgehog = new LinkedList<>();
        water = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            char[] input = st.nextToken().toCharArray();
            for(int j = 0; j < m; j++) {
                arr[i][j] = input[j];

                if(input[j] == 'S') {
                    hedgehog.add(new int[] {i, j});
                }

                if(input[j] == '*') {
                    water.add(new int[] {i, j});
                }
            }
        }

        int dist = 0;
        while(true) {
            dist++;
            if(hedgehog.isEmpty()) {
                bw.write("KAKTUS");
                break;
            }

            Water();
            if(HedgeHog()) {
                bw.write(dist + "");
                break;
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static boolean HedgeHog() {
        int size = hedgehog.size();
        for(int i = 0; i < size; i++) {
//        while(!hedgehog.isEmpty()) {
            int[] w = hedgehog.poll();

            for(int k = 0; k < 4; k++) {
                int y = w[0] + dy[k];
                int x = w[1] + dx[k];

                if(y >= 0 && y < n && x >= 0 && x < m) {
                    if(arr[y][x] == 'D') {
                        hedgehog.add(new int[] {y, x});
                        return true;
                    }

                    if(arr[y][x] == '.') {
                        arr[y][x] = 'S';
                        hedgehog.add(new int[] {y, x});
                    }
                }
            }
        }
        return false;
    }

    private static void Water() {
        int size = water.size(); // water.size()는 가변이기에 별도로 선언 
        for(int i = 0; i < size; i++) { // 인접한 곳만 처리하기 위함
//        while(!water.isEmpty()) {
            int[] w = water.poll();

            for(int k = 0; k < 4; k++) {
                int y = w[0] + dy[k];
                int x = w[1] + dx[k];

                if(y >= 0 && y < n && x >= 0 && x < m) {
                    if(arr[y][x] == '.') {
                        arr[y][x] = '*';
                        water.add(new int[] {y, x});
                    }
                }
            }
        }
    }
}