[백준 3055, Java] 탈출

문제

www.acmicpc.net/problem/3055

 

풀이

1초마다 물과 고슴도치가 이동하는 것을 그림으로 나타내면 아래와 같다

물과 고슴도치가 이동할 수 있는 조건이 다르므로 (물은 동굴을 지나갈 수 없고, 고슴도치는 동굴을 지나갈 수 있다) 물이 이동하는 위치를 넣는 큐하나와 고슴도치가 이동하는 큐하나, 총 2개의 큐를 이용해 bfs를 진행하면 된다.

 

 그런데 이때 while(queueWater.isEmpty)를 조건으로 탐색을 하면, 1초에 해당하는 물만 이동하는게 아닌게 된다. 따라서 second라고 하는 변수를 하나 선언해서 second 값에 해당하는 거리를 이동한 물, 고슴도치만 이동하게한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Point{
    int x, y, distance;
    public Point(int x, int y, int distance){
        this.x = x;
        this.y = y;
        this.distance =distance;
    }
}
public class Main {
    public static int R;
    public static int C;
    public static char[][] map;
    public static boolean[][] visited;
    public static final char EMPTY = '.';
    public static final char WATER = '*';
    public static final char STONE = 'X';
    public static final char CAVE  = 'D';
    public static final char DOCHI = 'S';
    public static Queue<Point> queueDochi;
    public static Queue<Point> queueWater;
    public static int caveX;
    public static int caveY;
    public static int[] dx = {-1,0,1,0};
    public static int[] dy = {0,1,0,-1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        String line;

        st = new StringTokenizer(br.readLine()," ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        visited = new boolean[R][C];
        queueWater = new LinkedList<>();
        queueDochi = new LinkedList<>();

        for(int r = 0; r<R ; r++){
            line = br.readLine();
            for(int c=0; c<C; c++){
                char value = line.charAt(c);
                if(value == 'S'){
                    map[r][c] = EMPTY;
                    queueDochi.add(new Point(r, c, 0));
                    visited[r][c] = true;
                }
                else if(value ==WATER){
                    queueWater.add(new Point(r,c,0));
                    map[r][c] =value;
                }
                else if(value == CAVE){
                    map[r][c] = CAVE;
                    caveX = r;
                    caveY = c;
                }
                else{
                    map[r][c] = value;
                }
            }
        }

        int result = bfs();
        if(result ==-1){
            bw.write("KAKTUS");
        }
        else {
            bw.write(String.valueOf(result));
        }
        bw.flush();



    }
    // 처음 도치의 위치에서 동굴로 갈 수 있는지 없는지의 여부
    public static int bfs(){
        int second = 0;

        //물확산
        while(true){

            while(!queueWater.isEmpty() && queueWater.peek().distance==second){
                Point currentWater = queueWater.poll();
                for(int d = 0; d<4 ;d++){
                    int nx = currentWater.x + dx[d];
                    int ny = currentWater.y + dy[d];

                    if(nx>=0 && ny>=0 && nx<R && ny<C){
                        if(map[nx][ny]==EMPTY){
                            map[nx][ny] = WATER;
                            queueWater.add(new Point(nx, ny, currentWater.distance+1));
                        }
                    }
                }
            }

            //고슴도치 이동
            while(!queueDochi.isEmpty() && queueDochi.peek().distance==second){
                Point currentDochi = queueDochi.poll();
                if(currentDochi.x ==caveX && currentDochi.y == caveY){
                    return currentDochi.distance;
                }
                else{
                    for(int d= 0; d<4; d++){
                        int nx = currentDochi.x + dx[d];
                        int ny = currentDochi.y + dy[d];

                        if(nx>=0 && nx<R && ny>=0 && ny<C){
                            if(map[nx][ny] == EMPTY || map[nx][ny] == CAVE){
                                if(!visited[nx][ny]){
                                    visited[nx][ny] = true;
                                    queueDochi.add(new Point(nx, ny, currentDochi.distance+1));
                                }
                            }
                        }
                    }
                }
            }
            //더이상 이동 할 수 있는 도치가 없으면
            if(queueDochi.isEmpty()){
                break;
            }
            second++;
        }
        return -1;
    }
}