백준 3055 탈출

문제 바로가기

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.
티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.
매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.
티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.
고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

접근

딱 보아도 BFS, DFS 문제다.

1. 고슴도치의 이동과 동시에 물도 번져나간다. 즉 두 개체의 이동의 변화를 체크해줘야한다.

2. 고슴도치는 물이 찰 예정인 칸으로 이동 할 수 없다고 했다. 그렇다면 물이 먼저 차오른 다음에 고슴도치가 움직인다고 생각해도 문제가 없다.

3. 고슴도치와 비버의 굴은 한 개씩 있지만 물은 여러군데 있을 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_3055_탈출 {
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    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));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        Node hedgeHog = null; // 고슴도치의 위치
        Node beaver = null; // 비버 굴 위치
        List<Node> water = new ArrayList<>(); // 물이 있는 곳의 위치

        char[][] map = new char[R][C]; // 지도

        // 고슴도치, 비버 굴, 물 위치 정보를 기록
        for (int i = 0; i < R; i++) {
            String x = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = x.charAt(j);
                if (map[i][j] == 'S')
                    hedgeHog = new Node(i, j, 0);
                else if (map[i][j] == 'D')
                    beaver = new Node(i, j, 0);
                else if (map[i][j] == '*')
                    water.add(new Node(i, j, 0));
            }
        }
        int k = bfs(map, hedgeHog, water, beaver);
        if (k == -1)
            sb.append("KAKTUS");
        else
            sb.append(k);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static int bfs(char[][] map, Node hedgeHog, List<Node> water, Node beaver) {
        Queue<Node> hq = new LinkedList<>(); // 고슴도치의 위치가 들어가는 큐
        Queue<Node> wq = new LinkedList<>(); // 물의 위치가 들어가는 큐
        hq.offer(hedgeHog);
        for (Node a : water)
            wq.offer(a);

        // 매 분 마다 이동하면서 고슴도치와 물의 이동변화를 체크 해주어야한다.
        // 그러므로 현재 큐에 들어있는 정보의 수 만큼만 반복을 수행해야한다.
        int hedgeSize = hq.size();
        int waterSize = wq.size();

        while (!hq.isEmpty()) {
            while (waterSize-- > 0) {
                Node curW = wq.poll(); // 현재 물의 위치

                // 4방 탐색
                for (int i = 0; i < 4; i++) {
                    int nwx = curW.x + dx[i]; // 다음 물의 위치의 x,y 값
                    int nwy = curW.y + dy[i];

                    // 배열 범위 밖이면 continue
                    if (nwx < 0 || nwx == R || nwy < 0 || nwy == C)
                        continue;

                    // 다음 위치가 물 or 돌 or 비버의 굴 이라면 continue;
                    if (map[nwx][nwy] == '*' || map[nwx][nwy] == 'X' || 
                    	map[nwx][nwy] == 'D')
                        continue;

                    // 위의 조건에 해당되지 않는다면 다음 위치는 물이 된다
                    // map[nwx][nwy]의 값이 S여도 상관이 없다. 물이 된다는건 
                    // 그 경로로 고슴도치가 이동하지 않는 다는 뜻이므로
                    map[nwx][nwy] = '*';

                    // 큐에 삽입
                    wq.offer(new Node(nwx, nwy, 0));
                }
            }
            // 다음에 수행할 반복 횟수를 저장
            waterSize = wq.size();

            while (hedgeSize-- > 0) {
                Node curH = hq.poll(); // 현재 고슴도치 위치

                // 고슴도치가 비버의 굴의 위치에 도달했다면 즉 최단경로이므로 cnt를 리턴
                if (curH.x == beaver.x && curH.y == beaver.y)
                    return curH.cnt;

                // 4방 탐색
                for (int i = 0; i < 4; i++) {
                    int nhx = curH.x + dx[i];// 고슴도치의 다음위치의 x,y 좌표
                    int nhy = curH.y + dy[i];

                    // 배열 범위 밖이면 continue
                    if (nhx < 0 || nhx == R || nhy < 0 || nhy == C)
                        continue;

                    // 다음 위치가 물 or 돌 or 고슴도치의 자취 라면 continue;
                    if (map[nhx][nhy] == '*' || map[nhx][nhy] == 'X' || 
                    	map[nhx][nhy] == 'S')
                        continue;

                    // 위의 조건에 해당되지 않는다면 다음 위치는 S가 된다
                    map[nhx][nhy] = 'S';

                    // 큐에 삽입
                    hq.offer(new Node(nhx, nhy, curH.cnt + 1));
                }
            }
            hedgeSize = hq.size();
        }
        return -1;
    }

    static class Node {
        // x좌표, y좌표, 이동한 횟수
        int x, y, cnt;

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