백준 3055. 탈출 :: 돼지개발자

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

"순서를 잘 생각한 BFS 두개."

먼저 물과 고슴도치를 이동 시키기 위해 두개의 Queue를 준비한다. 두개의 queue는 각 time 마다. 상하좌우로 이동할 것이다.

이때 물과 고슴도치 중 어떤 것을 먼저 움직여야 할까? 문제에 조건에 따르면 다음 시간에 물이 찰 곳에는 고슴도치가 이동하지 못한다고 했으므로, 물을 먼저 이동 시켜주고, 물이 찰 곳에 고슴도치가 이동하지 못하도록 해주어야 한다.

(만약 고슴도치가 수영을 N 번 할 수 있다고 한다면 문제가 어려워 질거같다... ) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int R,C;
    static boolean [][] visited;
    static char[][] map;
    static int ex,ey;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    
    static Queue<Integer> waters = new LinkedList<Integer>();
    static Queue<Integer> mans = new LinkedList<Integer>();
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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];
        
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp[j];
                
                if(temp[j] == 'S') {
                    mans.add(i);
                    mans.add(j);
                    visited[i][j] = true;
                    map[i][j] = '.';
                }
                else if(temp[j] == '*') {
                    waters.add(i);
                    waters.add(j);
                }
                else if(temp[j] == 'D') {
                    ex = i;
                    ey = j;
                }
            }
        }
        int cnt = 0;
        boolean ok = false;
        
        loop : while(!mans.isEmpty()) {
            
            int size = waters.size()/2;
            for (int s = 0; s < size; s++) {
                int x = waters.poll();
                int y = waters.poll();
                
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    
                    if(!isRange(nx, ny) || map[nx][ny] != '.')
                        continue;
                    
                    map[nx][ny] = '*';
                    waters.add(nx);
                    waters.add(ny);
                }
            }
            
            size = mans.size()/2;
            
            for (int s = 0; s < size; s++) {
                int x = mans.poll();
                int y = mans.poll();
                
                if(x == ex && y == ey ) {
                    ok = true;
                    break loop;
                }
                
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    
                    if(!isRange(nx, ny)  || visited[nx][ny] || map[nx][ny] == '*' || map[nx][ny] == 'X')
                        continue;
                    
                    visited[nx][ny] = true;
                    mans.add(nx);
                    mans.add(ny);
                }
            }
            
            cnt ++;
        }
        System.out.println(ok ? cnt : "KAKTUS");
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= R || y < 0 || y >= C) return false;
        return true;
    }
}