백준 3055 탈출 자바(java)

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

3055번: 탈출

 

풀이 방법

최소 시간, 즉 최단 거리를 구하는 문제이므로 BFS를 사용한다.

물 이동을 위해 물이 있는 칸의 좌표가 필요하므로 좌표들을 따로 water 큐에 저장하여 관리하였다.

 

1. 큐에 고슴도치가 있는 S칸의 좌표와 시간 배열 [x, y, t] 을 삽입한다. (처음 시간 t는 0이다.)

2. 물을 이동시킨다. 현재 물이 차있는 지역의 좌표를 water 큐에서 꺼내어 인접한 비어있는 칸을

    물로 변경한 후 변경된 새로운 칸들은 water 큐에 삽입하여 상태를 갱신한다.

3. 큐에 있는 요소를 하나씩 모두 꺼내어 해당 칸의 인접한 칸 중 고슴도치가 아직 방문하지 않았으면서

    물과 돌이 없는 칸의 좌표와 시간 [nx, ny, t+1] 을 이동 가능한 칸 리스트에 삽입하고 방문 체크한다.

4. 이동 가능한 칸 리스트에 있는 요소를 큐에 모두 삽입해준 후 다시 2번의 물 이동부터 반복한다.

5. 이동 가능한 칸 리스트 중 D칸이 있다면 탐색 종료한다.

 

만약,  D칸을 아직 만나지 못했는데 이동할 수 있는 칸이 없다면 4번에서 큐에 삽입되는 요소가 없어 큐가 빈 상태가 되므로 while문 반복 조건을 큐가 빈 상태가 아닐 때까지로 설정해놓는 다면 자동으로 루프가 종료된다.

 

코드

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

public class Main {

    static Character[][] map;
    static int R, C;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        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 Character[R][C];
        boolean[][] visited = new boolean[R][C]; // 고슴도치 방문 체크
        Queue<int[]> water = new LinkedList<>();
        int x = 0;
        int y = 0;

        for(int i=0; i<R; i++) {
            String line = br.readLine();
            for(int j=0; j<C; j++) {
                map[i][j] = line.charAt(j);
                if(map[i][j] == 'S') {
                    x = i;
                    y = j;
                }
                if(map[i][j] == '*') {
                    water.add(new int[]{i, j});
                }
            }
        }

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y, 0});
        visited[x][y] = true;

        int answer = 0;
        boolean arrived = false;
        while(!arrived && !q.isEmpty()) {
            // 물 확장
            spread(water);
            // 고슴도치 이동
            List<int[]> moved = new ArrayList<>(); // 이동 가능한 칸 리스트
            while(!q.isEmpty()) {
                int[] cur = q.poll();
                for(int i=0; i<4; i++) {
                    int nx = cur[0] + dx[i];
                    int ny = cur[1] + dy[i];
                    if(nx < 0 || nx >= R || ny < 0 || ny >= C) {
                        continue;
                    }
                    // 물과 돌이 없고 방문하지 않은 칸이면 이동 가능
                    if(!visited[nx][ny] && map[nx][ny] != '*' && map[nx][ny] != 'X') {
                        visited[nx][ny] = true;
                        moved.add(new int[]{nx, ny, cur[2]+1});
                    }
                }
            }

            for(int[] m : moved) {
                // 비버의 굴에 도착하면
                if(map[m[0]][m[1]] == 'D') {
                    answer = m[2];
                    arrived = true;
                    break;
                }
                q.add(m);
            }
        }

        if(arrived) {
            System.out.println(answer);
        } else {
            System.out.println("KAKTUS");
        }
    }

    public static void spread(Queue<int[]> water) {
        Queue<int[]> next = new LinkedList<>(); // 물이 이동한 새로운 칸
        while(!water.isEmpty()) {
            int[] w = water.poll();
            for(int i=0; i<4; i++) {
                int nx = w[0] + dx[i];
                int ny = w[1] + dy[i];
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                    continue;
                }
                // 빈 곳이면 물이 이동
                if(map[nx][ny] == '.') {
                    map[nx][ny] = '*';
                    next.add(new int[]{nx, ny});
                }
            }
        }
        while(!next.isEmpty()) { // 다음 상태 갱신
            water.add(next.poll());
        }
    }
}