[백준 Gold 4] 3055 탈출 - Java

문제링크 : https://www.acmicpc.net/problem/3055

3055번: 탈출

 

접근 과정 : 

• 일반적인 BFS 방식으로 접근
• 물이 찰 공간으로 고슴도치가 이동할 수 없다.
• 시간++ -> 물 이동 -> 고슴도치 이동 순으로 반복해서 가장 빠른 시간을 탐색
• 만약 고슴도치가 더 이상 이동할 수 없다면, 비버의 집에 갈 수 없다!!

 

소스 코드 및 결과 : 

package BOJ;

/* 
    탈출 
*/

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

public class BOJ3055 {

    static int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        char[][] forest = new char[R][C];

        Queue<int[]> hedgehog = new LinkedList<>();
        Queue<int[]> water = new LinkedList<>();
        boolean[][] visit = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                forest[i][j] = input.charAt(j);

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

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

            }
        }

        int count = 0;

        while (!hedgehog.isEmpty()) {

            count++;

            // 물 이동
            int size = water.size();
            while (size-- > 0) {

                int[] w = water.poll();

                for (int i = 0; i < 4; i++) {
                    int wr = w[0] + move[i][0];
                    int wc = w[1] + move[i][1];

                    if (wr < 0 || wr >= R || wc < 0 || wc >= C || forest[wr][wc] != '.') {
                        continue;
                    }

                    forest[wr][wc] = '*';
                    water.add(new int[] { wr, wc });
                }
            }

            // 고슴도치 이동
            size = hedgehog.size();
            while (size-- > 0) {

                int[] h = hedgehog.poll();

                for (int i = 0; i < 4; i++) {
                    int hr = h[0] + move[i][0];
                    int hc = h[1] + move[i][1];

                    if (hr < 0 || hr >= R || hc < 0 || hc >= C || visit[hr][hc] || forest[hr][hc] == '*'
                            || forest[hr][hc] == 'X') {
                        continue;
                    }

                    if (forest[hr][hc] == 'D') {
                        System.out.println(count);
                        return;
                    }

                    visit[hr][hc] = true;
                    hedgehog.add(new int[] { hr, hc });

                }
            }

        }

        System.out.println("KAKTUS");

    }

}

 

 

P.S

물이 없는 경우가 존재하나 봄

티떡숲에 홍수를 일으킨다는데..., 티떡숲 지도에 물이 주어지지 않다니...