[BOJ] 백준 3005. 탈출

문제

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

3055번: 탈출

---

풀이

 하나의 지도 배열에 BFS가 두 번 쓰이는 문제입니다. 전형적인 BFS 문제에 물이 퍼지는 것을 고려해야하는 문제입니다. 

 

 특정 좌표에 몇 초 후에 물이 도달하는 지는 BFS를 통해 미리 구할 수 있습니다. time[][] 이라는 배열을 선언하여, 물이 미래에 도착할 시간을 저장하고, 고슴도치의 시간(depth)와 물이 도착하는 시간(time[][])을 비교해 문제를 해결했습니다.

---

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N,M;
    static char[][] map;
    static int[][] time;
    static boolean[][] visited;
    static boolean[][] visited1;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static  Queue<int[]> queue = new LinkedList<>();
    static  Queue<int[]> waters = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new char[N][M];
        visited = new boolean[N][M];
        visited1 = new boolean[N][M];
        time = new int[N][M];

        for(int r=0;r<N;r++){
            String str = sc.next();
            for(int c=0;c<M;c++){
                time[r][c] = 2500;
                map[r][c] = str.charAt(c);
                if(map[r][c] == 'S'){
                    queue.add(new int[]{r,c,1});
                    visited[r][c] = true;
                }
                if(map[r][c]=='*'){
                    waters.add(new int[]{r,c,1});
                    time[r][c] = -1;
                }
            }
        }
        waterCheck();
        int ans = bfs();

        if(ans==-1) System.out.println("KAKTUS");
        else System.out.println(ans-1);
    }
    static int bfs(){
        while(!queue.isEmpty()){
            int[] info = queue.poll();
            int r = info[0];
            int c = info[1];
            int depth = info[2];

            if(map[r][c]=='D'){
                return depth;
            }
            for(int i = 0; i<4;i++){
                int idr = r+dr[i];
                int idc = c+dc[i];
                if(idr<0||idc<0||idr>=N||idc>=M) continue;
                if(visited[idr][idc]) continue;
                if(map[idr][idc]=='*'||map[idr][idc]=='X') continue;
                if(depth<time[idr][idc]) {
                   visited[idr][idc] = true;
                    queue.add(new int[]{idr, idc, depth + 1});
                }
            }
        }
        return -1;
    }
    static void waterCheck(){
        while(!waters.isEmpty()){
            int[] info = waters.poll();
            int r = info[0];
            int c = info[1];
            int depth = info[2];
            for(int i = 0; i<4;i++){
                int idr = r+dr[i];
                int idc = c+dc[i];
                if(idr<0||idc<0||idr>=N||idc>=M) continue;
                if(visited1[idr][idc]) continue;
                if(map[idr][idc]=='D'||map[idr][idc]=='X') continue;
                if(map[idr][idc]=='.'||map[idr][idc]=='S'){
                    visited1[idr][idc] = true;
                    time[idr][idc] = depth;
                    waters.add(new int[]{idr,idc,depth+1});
                }
            }
        }
    }
}