[BOJ/Java] 3055. 탈출

[BOJ/Java] 3055. 탈출

3055번: 탈출

---

문제 해석

이 문제는 고슴도치가 물이 차오르는 동굴에서 탈출구로 이동하는 최소 시간을 찾는 시뮬레이션 문제이다. 동굴은 격자로 표현되며, 고슴도치는 매 초마다 인접한 네 방향으로 이동할 수 있다. 물도 매 초마다 인접한 네 방향으로 확장된다. 고슴도치는 물이 있는 칸이나 돌이 있는 칸으로 이동할 수 없으며, 탈출구에 도달하면 게임이 종료된다. 탈출이 불가능한 경우도 고려해야 한다.

풀이 과정

Java 코드는 BFS(너비 우선 탐색)를 사용하여 고슴도치가 탈출구에 도달할 수 있는 최소 시간을 계산한다. Point 클래스는 위치와 시간을 표현하며, ArrayDeque는 BFS 탐색에 사용되는 큐이다.

 

1. 입력 처리: 격자의 크기를 입력받고, 각 칸의 상태를 입력받는다. 물의 위치는 큐에 먼저 추가하고, 고슴도치의 시작 위치도 저장한다.
2. 탐색 실행: go() 메소드에서 BFS를 실행하여 고슴도치가 탈출구에 도달할 수 있는지 탐색한다. 각 포인트에서 가능한 이동 방향을 검사하고 조건에 따라 큐에 추가한다.
3. 결과 처리: 고슴도치가 탈출구에 도달하면 이동 시간을 출력하고, 탈출이 불가능하면 "KAKTUS"를 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No3055;

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

public class Main {
    private static int R; // 격자의 행 크기
    private static int C; // 격자의 열 크기
    private static char[][] map; // 격자 정보
    private static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 이동 방향 벡터
    private static Point start; // 고슴도치 시작 위치
    private static ArrayDeque<Point> q; // BFS를 위한 큐
    private static int ans = -1; // 결과 값
    private static StringBuilder sb = new StringBuilder(); // 출력을 위한 문자열 빌더

    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());
        R = Integer.parseInt(st.nextToken()); // 행 입력
        C = Integer.parseInt(st.nextToken()); // 열 입력
        map = new char[R][C];
        q = new ArrayDeque<>();
        for (int i = 0; i < R; i++) {
            String row = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = row.charAt(j);
                if (map[i][j] == '*') q.offer(new Point(i, j, 0)); // 물 위치 큐에 추가
                if (map[i][j] == 'S') start = new Point(i, j, 0); // 시작 위치 저장
            }
        }

        sol(); // 솔루션 함수 실행
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        ans = go(); // BFS 실행
        if (ans == -1) sb.append("KAKTUS"); // 탈출 불가
        else sb.append(ans); // 탈출 시간 출력
    }

    private static int go() {
        q.add(start); // 고슴도치 위치 추가
        while(!q.isEmpty()) {
            Point p = q.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if (map[nx][ny] == 'X') continue; // 돌이면 이동 불가
                if (map[nx][ny] == '.') { // 비어있는 칸이면 이동
                    q.offer(new Point(nx, ny, p.t + 1));
                    if (map[p.x][p.y] == '*') map[nx][ny] = '*'; // 물 확장
                    if (map[p.x][p.y] == 'S') map[nx][ny] = 'S'; // 고슴도치 이동
                } else if (map[nx][ny] == 'D') { // 탈출구 도달
                    if (map[p.x][p.y] == 'S') return p.t+1; // 탈출 시간 반환
                }
            }
        }
        return -1; // 탈출 불가
    }

    static class Point {
        int x, y, t; // 위치 (x, y)와 시간 t

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

시간 복잡도 분석

시간 복잡도는 𝑂(𝑅×𝐶)로, 격자의 모든 칸을 최대 한 번씩 방문하기 때문에 이와 같이 결정된다.

느낀점

이 문제를 통해 격자와 BFS를 활용한 시뮬레이션 문제를 다루는 능력이 향상되었다. 특히, 다양한 타입의 객체를 동시에 처리하는 BFS 구현의 복잡성을 경험하면서 알고리즘 설계에 있어 더 깊이 있게 생각할 필요성을 느꼈다. 또한, 예외 상황을 효과적으로 처리하는 방법에 대해 다시 한번 고민하는 계기가 되었다.