[BOJ] 백준 [3055] 탈출 JAVA

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

3055번: 탈출

[문제]

[풀이]

물이 찰 예정엔 고슴도치가 이동불가 => 물 먼저 처리할 것.
즉 , 탐색을 하기위해 우선순위를
1. 진행일수 2. 처리순서 로 하기위해서 우선순위큐를 이용한 BFS로 탐색하였다.

물탐색 : map이 '.' 이거나 'S' 인 경우에만 진행후 , '*'로 마킹.
고슴도치탐색 : map이 '.' 이거나 'D' 인 경우에만 진행후 'S'로 마킹.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static int w,h;
    static char[][] map;
    static Point end;
    static int[] dx={0,0,1,-1},dy={1,-1,0,0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        h = input[0]; w = input[1];
        map = new char[h][w];
        PriorityQueue<Point> q = new PriorityQueue<Point>();
        for(int i=0;i<h;i++) {
            map[i] = br.readLine().toCharArray();
            for(int j=0;j<w;j++){
                switch (map[i][j]){
                    case 'D' -> end =  new Point(j,i,2,0);
                    case '*' -> q.add(new Point(j,i,0,0));
                    case 'S' -> q.add(new Point(j,i,1,0));
                }
            }
        }
 
        while (!q.isEmpty()){
            Point cur = q.poll();
            if(cur.y == end.y && cur.x==end.x){
                System.out.println(cur.day);
                return;
            }
 
            // 물 처리
            if(cur.type==0){
                for(int i=0;i<dx.length;i++){
                    int nextX = cur.x+dx[i];
                    int nextY = cur.y+dy[i];
 
                    if(!isRange(nextX,nextY)) continue;
 
                    if(map[nextY][nextX]=='.' || map[nextY][nextX]=='S'){
                        map[nextY][nextX] = '*';
                        q.add(new Point(nextX,nextY, cur.type, cur.day+1));
                    }
                }
            }
 
            // 고슴도치 처리
            if(cur.type==1){
                for(int i=0;i<dx.length;i++){
                    int nextX = cur.x+dx[i];
                    int nextY = cur.y+dy[i];
 
                    if(!isRange(nextX,nextY)) continue;
 
                    if(map[nextY][nextX]=='.' || map[nextY][nextX]=='D'){
                        q.add(new Point(nextX,nextY, cur.type, cur.day+1));
                        map[nextY][nextX] = 'S';
                    }
                }
            }
 
        }
        System.out.println("KAKTUS");
 
    }
 
    private static boolean isRange(int x, int y) {
        return x>=0&&y>=0&&x<w&&y<h;
    }
 
    private static class Point implements Comparable<Point>{
        int x,y,day,type;
        // type : [0:water] [1:viber] [2:cave]
        public Point(int x, int y, int type, int day) {
            this.x = x;
            this.y = y;
            this.day = day;
            this.type = type;
        }
 
        @Override
        public int compareTo(Point o) {
            if(this.day==o.day) return this.type-o.type;
            return this.day-o.day;
        }
    }
}