[백준] 3055번 탈출 Java

문제 링크

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

알고리즘: BFS

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

풀이

고슴도치를 인접한 칸으로 이동시키고, 물을 인접한 칸으로 침범시킨다.
이 방법을 반복해서 도달할 수 있다면 최단 거리를 출력하고, 도달할 수 없다면 -1을 출력해준다.

소스 코드

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

class Node {
    int x,y,c;
    Node(int x, int y, int c) {
        this.x = x;
        this.y = y;
        this.c = c;
    }
}

class Coordinate {
    int x,y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static final int dx[] = {0,0,-1,1};
    static final int dy[] = {-1,1,0,0};
    static char map[][];
    static boolean h_visited[][];
    static boolean w_visited[][];
    static ArrayList<Coordinate> water_location = new ArrayList<Coordinate>();
    static int R,C;
    static Coordinate hgh, cave;
    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];
        h_visited= new boolean[R][C];
        w_visited= new boolean[R][C];
        for(int i=0; i<R; i++) {
            String s = br.readLine();
            for(int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
                if(map[i][j] == '*') {
                    water_location.add(new Coordinate(j,i));
                    w_visited[i][j] = true;
                } else if(map[i][j] == 'S') {
                    hgh = new Coordinate(j,i);
                } else if(map[i][j] == 'D') {
                    cave = new Coordinate(j,i);
                }
            }
        }
        int answel = BFS();
        if(answel == -1) {
            System.out.println("KAKTUS");
        } else {
            System.out.println(answel);
        }
    }
    
    static int BFS() {
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(hgh.x, hgh.y, 0));
        while(!que.isEmpty()) {
            int qs = que.size();
            h_visited = new boolean[R][C]; //초기화
            for(int i=0; i<qs; i++) {
                Node v = que.poll();
                if(v.x == cave.x && v.y == cave.y) {
                    return v.c;
                }
                if(map[v.y][v.x] == '*') {
                    //현재 고슴도치 위치가 물로 차있으면 
                    continue;
                }
                for(int j=0; j<dx.length; j++) {
                    int nx = v.x + dx[j];
                    int ny = v.y + dy[j];
                    if((nx>=0 && nx<=C-1) && (ny>=0 && ny<=R-1)) {
                        if(map[ny][nx] != 'X' && map[ny][nx] != '*' && !h_visited[ny][nx]) {
                            h_visited[ny][nx] = true;
                            que.add(new Node(nx, ny, v.c+1));
                        }
                    }
                }
            }
            move_water();
        }
        return -1;
    }
    
    static void move_water() {
        ArrayList<Coordinate> nWater_location = new ArrayList<Coordinate>();
        for(int i=0; i<water_location.size(); i++) {
            for(int j=0; j<dx.length; j++) {
                int nx = water_location.get(i).x + dx[j];
                int ny = water_location.get(i).y + dy[j];
                if((nx>=0 && nx<=C-1) && (ny>=0 && ny<=R-1)) {
                    if(map[ny][nx] != 'X' && map[ny][nx] != 'D' && !w_visited[ny][nx]) {
                        w_visited[ny][nx] = true;
                        map[ny][nx] = '*';
                        nWater_location.add(new Coordinate(nx, ny));
                    }
                }
            }
        }
        water_location = nWater_location;
    }
}