[백준] 3055 탈출 - Java

 

 

 

물이 전이되는 조건 때문에 처리해줘야 하는 요소가 많다.

 

일단 최단시간을 구하는게 목적이니, bfs를 돌리면서 최단 시간을 갱신하면 풀 수 있을 것 같다.

 

고슴도치는 물이 전이된 곳에 갈 수 없으니 물에 대한 bfs를 먼저 돌려 언제 물이 해당 위치에 전이되는지 기록하자.

 

그 후는 항상 하던대로 고슴도치에 대한 bfs를 수행하면 된다.

 

 

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

public class Main {

    static int N;    
    static int M;
    static char[][] map;
    
    
    static int[][] dist_water;
    static int[][] dist_hedgehog;
    static boolean[][] visit;

    static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};    
    

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        dist_water = new int[N][M];
        dist_hedgehog = new int[N][M];
        visit = new boolean[N][M];
        
        for(int i=0; i<N; i++){
            String tmp = br.readLine();
            for(int j=0; j<M; j++){
                map[i][j] = tmp.charAt(j);
            }
        }

        bfs_water();
        bfs_hedgehog();

        for(int i =0; i<N; i++){
            for(int j=0; j<M; j++){                                    
                if(map[i][j] == 'D'){
                    if(dist_hedgehog[i][j] == -1){
                        System.out.println("KAKTUS");
                    }else{
                        System.out.println(dist_hedgehog[i][j]);
                    }
                }
            }
        }
        
        
    }

    static void bfs_water(){

        visit = new boolean[N][M];
        Queue<Integer> q = new LinkedList<>();

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                dist_water[i][j] = -1;
                if(map[i][j] == '*'){
                    q.add(i);
                    q.add(j);
                    dist_water[i][j] = 0;
                    visit[i][j] = true;
                }
            }
        }

        while(!q.isEmpty()){
            int r = q.poll();
            int c = q.poll();
            for(int i=0; i<4; i++){
                int nr = r + dir[i][0];
                int nc = c + dir[i][1];
                if(nr < 0 || nr >= N || nc < 0 || nc >= M){
                    continue;
                }
                if(map[nr][nc] != '.'){
                    continue;
                }
                if(visit[nr][nc]){
                    continue;
                }
                q.add(nr);
                q.add(nc);
                visit[nr][nc] = true;
                dist_water[nr][nc] = dist_water[r][c] + 1;
            }
        }
    }

    static void bfs_hedgehog(){
        Queue<Integer> q = new LinkedList<>();

        visit = new boolean[N][M];    

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                dist_hedgehog[i][j] = -1;
                if(map[i][j] == 'S'){
                    q.add(i);
                    q.add(j);
                    dist_hedgehog[i][j] = 0;
                    visit[i][j] = true;
                }
            }
        }

        while(!q.isEmpty()){
            int r = q.poll();
            int c = q.poll();
            for(int i=0; i<4; i++){
                int nr = r + dir[i][0];
                int nc = c + dir[i][1];
                if(nr < 0 || nr >= N || nc < 0 || nc >= M){
                    continue;
                }
                if(map[nr][nc] != '.' && map[nr][nc] != 'D'){
                    continue;
                }
                if(dist_water[nr][nc] != -1 && dist_water[nr][nc] <= dist_hedgehog[r][c] + 1){
                    continue;
                }
                if(visit[nr][nc]){
                    continue;
                }
                q.add(nr);
                q.add(nc);
                visit[nr][nc] = true;
                dist_hedgehog[nr][nc] = dist_hedgehog[r][c] + 1;
            }
        }
    }
}