[BOJ_3055] 탈출

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

3055번: 탈출

🏗️ 설계

• 각 칸에 물이 도달하는 시간을 저장하는 시간 배열을 BFS를 통해서 작성합니다
• 이후 고슴도치는 이동할 수 있는 칸을 탐색하여, 최소 시간에 비버의 소굴로 이동할 수 있는 방법을 BFS를 통해 탐색하도록 하였습니다.

📋 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int rowLen;
    static int colLen;
    static char[][] board;
    static int[][] timeBoard;
    static Queue<Pos> q = new ArrayDeque<>();
    static int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static class Pos {
        int row;
        int col;

        public Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    private static boolean check(int row, int col) {
        return row >= 0 && row < rowLen && col >= 0 && col < colLen;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rowLen = Integer.parseInt(st.nextToken());
        colLen = Integer.parseInt(st.nextToken());
        board = new char[rowLen][colLen];
        timeBoard = new int[rowLen][colLen];

        for (int i = 0; i < rowLen; i++) {
            Arrays.fill(timeBoard[i], 0x7fffffff);
        }

        boolean[][] visited = new boolean[rowLen][colLen];

        Pos start = new Pos(-1, -1);

        for (int i = 0; i < rowLen; i++) {
            String str = br.readLine();
            for (int j = 0; j < colLen; j++) {
                board[i][j] = str.charAt(j);
                if (board[i][j] == '*') {
                    q.add(new Pos(i, j));
                    visited[i][j] = true;
                    timeBoard[i][j] = 0;
                }
                if (board[i][j] == 'S') {
                    start.row = i;
                    start.col = j;
                }
            }
        }

        while (!q.isEmpty()) {
            Pos tmp = q.poll();
            for (int i = 0; i < 4; i++) {
                int nextRow = tmp.row + dir[i][0];
                int nextCol = tmp.col + dir[i][1];
                if (!check(nextRow, nextCol))
                    continue;
                if (visited[nextRow][nextCol])
                    continue;
                if (board[nextRow][nextCol] == '.' || board[nextRow][nextCol] == 'S') {
                    q.add(new Pos(nextRow, nextCol));
                    visited[nextRow][nextCol] = true;
                    timeBoard[nextRow][nextCol] = timeBoard[tmp.row][tmp.col] + 1;
                }
            }
        }

        visited = new boolean[rowLen][colLen];
        visited[start.row][start.col] = true;
        q.add(start);
        int time = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            time++;
            while (size --> 0) {
                Pos tmp = q.poll();

                for (int i = 0; i < 4; i++) {
                    int nextRow = tmp.row + dir[i][0];
                    int nextCol = tmp.col + dir[i][1];
                    if (!check(nextRow, nextCol)) {
                        continue;
                    }
                    if (visited[nextRow][nextCol]) {
                        continue;
                    }
                    if (board[nextRow][nextCol] == 'X') {
                        continue;
                    }
                    if (board[nextRow][nextCol] == 'D') {
                        System.out.println(time);
                        return;
                    }
                    if (board[nextRow][nextCol] == '.' && timeBoard[nextRow][nextCol] > time) {
                        q.add(new Pos(nextRow, nextCol));
                        visited[nextRow][nextCol] = true;
                    }
                }
            }
        }

        System.out.println("KAKTUS");
    }
}

👎 어려웠던 점

• Board 배열 하나로 시간을 저장해두고 탐색하고자 하였으나, char는 아스키 코드를 통해 탐색하기 때문에 X, *, . 등 들어오는 문자들을 처리하는 로직이 따로 필요했고, char에는 숫자를 0~9 까지밖에 넣을 수 없기 때문에 문제가 발생하였습니다.
• 이러한 문제를 해결하기 위해서 integer timeBoard 배열을 추가로 생성하게 되었습니다.

⏰ 사용한 메모리 / 시간

• Memory : 14284KB
• Time : 128ms