[백준] 3055. 탈출 (그래프 탐색 / Java)

[백준] 3055. 탈출

 

📌 풀이 과정

고슴도치(S)가 홍수가 난 티떱숲에서 비버의 굴(D)로 이동할 수 있는 가장 빠른 시간을 구하는 문제다.

매 분마다 물을 먼저 확장시켜, 고슴도치가 이동할 수 있는지 확인해야 하기에
물의 확장과 고슴도치의 이동을 각각의 큐에서 따로 관리 해야한다.

 

물의 큐(waterQ)

물이 퍼지는 모든 좌표를 저장하고, 매 턴마다 물이 퍼지는 과정을 먼저 처리한다.

 

고슴도치의 큐(hedgehogQ)

고슴도치가 이동하는 모든 좌표를 저장하고, 물이 퍼진 후 그 상태에서 고슴도치가 이동할 수 있는지를 확인한다.

 

💡 동작 흐름

1. 매 턴마다 물이 먼저 확장한다.

물의 큐에서 모든 물의 좌표를 하나씩 꺼내서 네 방향으로 확장 시킨다.

2. 물 확장 후 고슴도치 이동

물이 확장된 후 고슴도치가 갈 수 있는지 확인하고, 고슴도치 큐에서 이동할 수 있는 경로를 계속 탐색한다.

3. 고슴도치가 비버의 굴에 도달하면 종료

4. 고슴도치가 더 이상 이동할 수 없으면 "KAKTUS" 출력

 

 

✨ 제출 코드

메모리 : 14228 KB

시간 : 108 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int R, C;
    static char[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> waterQ = new LinkedList<>();
    static Queue<int[]> hedgehogQ = new LinkedList<>();

    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];
        visited = new boolean[R][C];  // 방문 체크 배열

        for(int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j = 0; j < C; j++) {
                if(map[i][j] == 'S') {
                    hedgehogQ.add(new int[]{i, j, 0});
                    visited[i][j] = true;  // 고슴도치의 초기 위치 방문 처리
                }
                if(map[i][j] == '*') waterQ.add(new int[]{i, j});
            }
        }

        int answer = bfs();
        System.out.println(answer >= 0 ? answer : "KAKTUS");
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }

    private static void flood(){
        int size = waterQ.size();

        for(int s = 0; s < size; s++){
            int[] cur = waterQ.poll();
            int x = cur[0];
            int y = cur[1];

            for(int d = 0; d < 4; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];

                if(!isValid(nx, ny) || map[nx][ny] == 'D' ||
                    map[nx][ny] == '*' || map[nx][ny] == 'X') continue;

                map[nx][ny] = '*';
                waterQ.add(new int[]{nx, ny});
            }
        }
    }

    private static int bfs(){
        while(!hedgehogQ.isEmpty()){

            // 1. 물 확장
            flood();

            // 2. 고슴도치 이동
            int size = hedgehogQ.size();

            for(int s = 0; s < size; s++){
                int[] cur = hedgehogQ.poll();
                int x = cur[0];
                int y = cur[1];
                int depth = cur[2];

                if(map[x][y] == 'D') return depth;  // 비버 굴에 도착하면 종료

                for(int d = 0; d < 4; d++){
                    int nx = x + dx[d];
                    int ny = y + dy[d];

                    if(!isValid(nx, ny) || visited[nx][ny] ||
                        map[nx][ny] == '*' || map[nx][ny] == 'X') continue;

                    hedgehogQ.add(new int[]{nx, ny, depth + 1});
                    visited[nx][ny] = true;  // 방문 처리
                }
            }
        }

        return -1;
    }
}