[백준] 3055번 탈출 (JAVA)

문제

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

3055번: 탈출

 

설명

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다.
물도 매 분마다 비어있는 칸으로 확장하는데 물이 있는 칸과 인접해있는 비어있는 칸은 물이 차게 된다.
고슴도치는 물로 차있는 칸으로 이동할 수 없고 물은 비버의 소굴로 이동할 수 없다. 둘 다 돌을 통과할 수 없다.

비어있는 곳, 물이 차있는 지역, 돌, 비버의 굴, 고슴도치의 위치를 저장할 map[][]을 만들어 저장한다.

고슴도치가 비버의 굴로 가장 빠르게 이동하기 위한 각각의 위치에 해당하는 시간을 저장할 dp[][]을 만든다.

 

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

 

위의 말은 이 문제에서 가장 핵심이 되는 말이다.

즉, 시간이 1초 지났을 때 고슴도치가 이동할 수 없는 곳은 물이 차 있는 곳 + 물의 상하좌우인 곳 + 돌 이다.

그러므로 먼저 물이 이동할 구역을 판단하고 후에 고슴도치가 이동할 구역을 판단해야 한다.

좌표 저장의 편의성을 위해 Point 클래스를 생성하고 물과 고슴도치의 좌표를 담을 Queue를 생성한다.

생성한 큐에 먼저 물의 좌표부터 큐에 넣고 마지막에 고슴도치의 좌표를 넣고 BFS를 진행한다.

static class Point {
    int x;
    int y;
    char type;

    public Point(int x, int y, char type) {
        this.x = x;
        this.y = y;
        this.type = type;
    }
}
    
static Queue<Point> queue;

Point start = null;    // 시작점
for (int r = 0; r < R; r++) {
    String line = br.readLine();
    for (int c = 0; c < C; c++) {
        map[r][c] = line.charAt(c);

        if (map[r][c] == '*') {
            // 물의 좌표를 큐에 넣는다
            queue.add(new Point(r, c, '*'));
        }
        else if (map[r][c] == 'S') {
            start = new Point(r, c, 'S');
        }
    }
}

// 마지막에 고슴도치의 좌표를 큐에 넣는다
queue.add(start);

bfs();

상하좌우 움직이는 좌표를 위해 MX, MY를 만든다.

더 이상 갈 수 있는 경로가 있는지에 대한 유무를 판단할 foundAnswer를 만든다.

큐에서 하나씩 빼내면서 물과 고슴도치가 갈 수 있는 좌표를 각각 판단하고 큐에 넣는다.

물 -> 비어있는 곳, 고슴도치가 있던 곳

고슴도치 -> 아직 방문하지 않은 비어있는 곳, 비버의 굴

위의 과정을 반복하면서 고슴도치가 비버의 굴에 도착할 때 해당 좌표의 dp[][]값을 출력한다.

모든 과정이 끝나 큐가 비어있는데도 고슴도치가 비버의 굴에 도달하지 못하면 "KAKTUS"를 출력한다.

static final int[] MX = { -1, 1, 0, 0};
static final int[] MY = { 0, 0, -1, 1};

static void bfs() {
    boolean foundAnswer = false;
    while (!queue.isEmpty()) {
        // 1. 큐에서 꺼내옴
        Point p = queue.poll();

        // 2. 목적지인가? (고슴도치가 D에 도착)
        if (p.type == 'D') {
            System.out.println(dp[p.x][p.y]);
            foundAnswer = true;
            break;
        }

        // 3. 연결된 곳을 순회 (상하좌우로 이동)
        for (int i = 0; i < 4; i++) {
            int tx = p.x + MX[i];
            int ty = p.y + MY[i];

            // 4. 갈 수 있는가? (공통 -> 맵 벗어나지 않고)
            if (0 <= tx && tx < R && 0 <= ty && ty < C) {
                if (p.type == '.' || p.type == 'S') {
                    // 4. 갈 수 있는가? (고슴도치 -> '.', 'D')
                    if ((map[tx][ty] == '.' || map[tx][ty] == 'D') && dp[tx][ty] == 0) {
                        // 5. 체크인 (고슴도치 -> dp)
                        dp[tx][ty] = dp[p.x][p.y] + 1;

                        // 6. 큐에 넣음
                        queue.add(new Point(tx, ty, map[tx][ty]));
                    }
                }
                else if (p.type == '*') {
                    // 4. 갈 수 있는가? (물 -> '.', 'S')
                    if (map[tx][ty] == '.' || map[tx][ty] == 'S') {
                        // 5. 체크인 (물 -> map)
                        map[tx][ty] = '*';

                        // 6. 큐에 넣음
                        queue.add(new Point(tx, ty, '*'));
                    }
                }
            }
        }
    }

    // 더 이상 갈 수 있는 길이 없으면
    if (!foundAnswer)
        System.out.println("KAKTUS");
}

 

전체 코드

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

public class Main {

    static final int[] MX = { -1, 1, 0, 0};
    static final int[] MY = { 0, 0, -1, 1};

    static int R, C;
    static char[][] map;
    static int[][] dp;
    static Queue<Point> queue;

    static class Point {
        int x;
        int y;
        char type;

        public Point(int x, int y, char type) {
            this.x = x;
            this.y = y;
            this.type = type;
        }
    }

    static void bfs() {
        boolean foundAnswer = false;
        while (!queue.isEmpty()) {
            // 1. 큐에서 꺼내옴
            Point p = queue.poll();

            // 2. 목적지인가? (고슴도치가 D에 도착)
            if (p.type == 'D') {
                System.out.println(dp[p.x][p.y]);
                foundAnswer = true;
                break;
            }

            // 3. 연결된 곳을 순회 (상하좌우로 이동)
            for (int i = 0; i < 4; i++) {
                int tx = p.x + MX[i];
                int ty = p.y + MY[i];

                // 4. 갈 수 있는가? (공통 -> 맵 벗어나지 않고)
                if (0 <= tx && tx < R && 0 <= ty && ty < C) {
                    if (p.type == '.' || p.type == 'S') {
                        // 4. 갈 수 있는가? (고슴도치 -> '.', 'D')
                        if ((map[tx][ty] == '.' || map[tx][ty] == 'D') && dp[tx][ty] == 0) {
                            // 5. 체크인 (고슴도치 -> dp)
                            dp[tx][ty] = dp[p.x][p.y] + 1;

                            // 6. 큐에 넣음
                            queue.add(new Point(tx, ty, map[tx][ty]));
                        }
                    }
                    else if (p.type == '*') {
                        // 4. 갈 수 있는가? (물 -> '.', 'S')
                        if (map[tx][ty] == '.' || map[tx][ty] == 'S') {
                            // 5. 체크인 (물 -> map)
                            map[tx][ty] = '*';

                            // 6. 큐에 넣음
                            queue.add(new Point(tx, ty, '*'));
                        }
                    }
                }
            }
        }

        // 더 이상 갈 수 있는 길이 없으면
        if (!foundAnswer)
            System.out.println("KAKTUS");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        dp = new int[R][C];
        queue = new LinkedList<>();

        Point start = null;    // 시작점
        for (int r = 0; r < R; r++) {
            String line = br.readLine();
            for (int c = 0; c < C; c++) {
                map[r][c] = line.charAt(c);

                if (map[r][c] == '*') {
                    queue.add(new Point(r, c, '*'));
                }
                else if (map[r][c] == 'S') {
                    start = new Point(r, c, 'S');
                }
            }
        }

        queue.add(start);

        bfs();
    }
}