[BOJ]3055번: 탈출

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

3055번: 탈출

 

분류 : BFS , 시뮬레이션

import java.io.*;
import java.math.*;
import java.util.*;
class Myscanner{
    BufferedReader br;
    StringTokenizer st;
    public Myscanner(){
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    String next(){
        while(st == null|| !st.hasMoreElements()){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    long nextLong(){
        return Long.parseLong(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
}

public class Main {
    public static Myscanner sc = new Myscanner();
    static int N,M,DX,DY,inf = Integer.MAX_VALUE;
    static char[][] forest;
    static int[][] biber,flood;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,-1,0,1};
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    public static void main(String[] args) throws IOException {
        N = sc.nextInt();
        M = sc.nextInt();
        forest = new char[N][M];
        biber = new int[N][M];
        flood = new int[N][M];
        Queue<Point> b = new LinkedList<>();
        Queue<Point> w = new LinkedList<>();
        for(int i=0;i<N;i++)
        {
            forest[i] = sc.next().toCharArray();
        }
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                flood[i][j]=inf;
                if(forest[i][j]=='S'){
                    b.offer(new Point(i,j));
                    biber[i][j]=1;
                }
                else if(forest[i][j]=='*')
                {
                    w.offer(new Point(i,j));
                    flood[i][j] =1;
                }
            }
        }
        
        wfs(w);
        int minute = bfs(b);
        if(minute == -1){
            out.println("KAKTUS");
        }
        else{
            out.println(minute);
        }
        out.flush();
    }
    private static void wfs(Queue<Point> w) {
        while(!w.isEmpty())
        {
            int size = w.size();
            for(int sz = 0; sz<size;sz++)
            {
                Point p = w.poll();
                int x = p.x;
                int y = p.y;
                for(int ar =0;ar<4;ar++)
                {
                    int cx = x+dx[ar];
                    int cy = y+dy[ar];
                    
                    if(cx>=0 && cx<N && cy>=0 && cy<M)
                        if(forest[cx][cy]!='X' && forest[cx][cy]!='D' && flood[cx][cy]==inf)
                        {
                            flood[cx][cy] = Math.min(flood[x][y]+1,flood[cx][cy]);
                            w.offer(new Point(cx,cy));
                        }
                }
            }
        }
    }
    private static int bfs(Queue<Point> b) {
        int seconds=1;
        while(!b.isEmpty())
        {
            int size = b.size();
            for(int sz = 0; sz<size;sz++)
            {
                Point p = b.poll();
                int x = p.x;
                int y = p.y;
                        
                for(int ar =0; ar<4;ar++)
                {
                    int cx = x+dx[ar];
                    int cy = y+dy[ar];
                    if(cx>=0 && cx<N && cy>=0 && cy<M){
                        if(forest[cx][cy]!='X' && flood[cx][cy]>biber[x][y]+1 && biber[cx][cy]==0 && forest[cx][cy]!='D')
                        {
                            biber[cx][cy]=biber[x][y]+1;
                            b.offer(new Point(cx,cy));
                        }
                        else if(forest[cx][cy]=='D'){
                            return seconds;
                        }
                    }
                }
            }
            seconds++;
        }
        
        return -1;
    }
}
class Point{
    int x,y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

 

 

내가 풀었던 불 문제나 다른 문제와 비슷한 형태의 bfs 문제이다.

물이 다른 곳으로 이동할 때의 걸리는 시간보다 고슴도치가 더 빨리 움직여 비버의 굴로 도착할 수 있는가 없는가를 해결하는 문제..

처음에 쓸데 없이 이상한 코드를 집어넣어서 시간 초과가 나왔고 지속적으로 수정하여 해결 완료