[JAVA] 백준 3055 탈출_BFS

 

문제:

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

 

 

접근 : 

 

 - 물을 퍼뜨린다. 만약 돌이 있거나 동굴인 경우에는 지나가지 못한다.

 

 - 두더지를 다음 경로로 이동시킨다. 만약 돌이 있거나 물이 있는 경우 지나가지 못한다.

 

 - 만약 두더지가 동굴로 들어간다면, 동굴까지 걸린 시간을 출력한다.

 

 - 만약 두더지가 동굴로 들어가지 못한다면, KAKTUS를 출력한다.

 

 

 

코드구현 :

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static boolean[][] waters;
    private static boolean[][] visited;
    private static Position finish;
    private static int ans = -1;

    private static final Position[] directions = {
            new Position(0,1), new Position(1,0), new Position(0,-1), new Position(-1,0)
    };

    private static class Position{
        private final int x;
        private final int y;

        public Position(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return this.x;
        }
        public int getY(){
            return this.y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Position position = (Position) o;
            return x == position.x && y == position.y;
        }
    }
    private static class Hedgehog{
        private final Position position;
        private final int move_time;
        public Hedgehog(Position position, int move_time){
            this.position = position;
            this.move_time = move_time;
        }
        public Position getPosition(){
            return this.position;
        }
        public int getMoveTime() {
            return this.move_time;
        }
    }

    private static Queue<Position> spreadWater(Queue<Position> before, int r, int c){
        int nx, ny;
        Position now;
        Queue<Position> after = new LinkedList<>();

        while (!before.isEmpty()){
            now = before.poll();

            for(Position dir : directions){
                nx = now.getX() + dir.getX();
                ny = now.getY() + dir.getY();

                if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if(waters[nx][ny]) continue;

                Position next = new Position(nx, ny);
                if(finish.equals(next)) continue;
                waters[nx][ny] = true;
                after.offer(next);
            }
        }
        return after;
    }
    private static Queue<Hedgehog> moveHegehog(Queue<Hedgehog> before, int r, int c){
        int nx, ny;
        Hedgehog now;
        Queue<Hedgehog> after = new LinkedList<>();

        while (!before.isEmpty()){
            now = before.poll();
            if(now.getPosition().equals(finish)){
                ans = now.getMoveTime();
                return after;
            }
            for(Position dir : directions){
                nx = now.getPosition().getX() + dir.getX();
                ny = now.getPosition().getY() + dir.getY();

                if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if(waters[nx][ny] || visited[nx][ny]) continue;

                visited[nx][ny] = true;
                after.offer(new Hedgehog(new Position(nx, ny), now.getMoveTime() + 1));
            }
        }
        return after;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input_one = br.readLine().split(" ");
        int r = Integer.parseInt(input_one[0]);
        int c = Integer.parseInt(input_one[1]);
        char[][] map = new char[r][c];
        waters = new boolean[r][c];
        visited = new boolean[r][c];

        String input_two;
        char temp;
        Queue<Hedgehog> q = new LinkedList<>();
        Queue<Position> before_water = new LinkedList<>();

        for(int i = 0 ; i < r ; i++) {
            input_two = br.readLine();
            for(int j = 0 ; j < c ; j++){
                temp = input_two.charAt(j);
                map[i][j] = temp;

                if(temp == 'S'){
                    q.offer(new Hedgehog(new Position(i, j), 0));
                    visited[i][j] = true;

                }
                else if(temp == 'D'){
                    finish = new Position(i, j);
                }
                else if(temp == '*') {
                    waters[i][j] = true;
                    before_water.offer(new Position(i, j));
                }else if(temp == 'X'){
                    waters[i][j] = true;
                    visited[i][j] = true;
                }
            }
        }

        while(!q.isEmpty()){
            // 물 먼저 퍼뜨리기
            before_water = spreadWater(before_water, r, c);
            //고슴도치 이동
            q = moveHegehog(q, r, c);
        }
        System.out.println(ans < 0 ? "KAKTUS" : ans);
    }
}