[ BFS / 정올 ] 1082 : 화염에서탈출

문제 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=362&sca=3040

뭐야 이 문제는!!!

BFS문제로 주로 좌표관련 문제가 많이 나옵니다. 그러한 문제들을 풀기위해 특정한 알고리즘 패턴을 암기해서 푸는 경우가 대부분인데 이 문제의 경우 너비탐색으로 고려해야하는 요소가 2개가 존재합니다.

[ 이동가능한 요소 ]

1. 지섭이 ( 용사? )
2. 불

[ 제약 조건 ]

1. 바위에는 불이나 지섭이가 이동할 수 없습니다.

2. 요새에는 불에 타지 않습니다.

위 조건들 중에서 이동가능한 요소는 다른 체스문제나 최단코스트 문제처럼 한 개가 아닌 2개가됩니다. 또한 같은 맵(차원)에서 이동하므로 서로의 위치가 겹치는 경우 또한 발생하죠.

[ 예를 들어서 ]

용사가 map( 10, 15 ) 로 이동한 경우

불도 또한 map ( 10, 15 ) 로 이동한 경우

이 경우는 용사가 간 다음날 그 위치에 불이 옮겼으므로 용사는... 아쉽게도... 세상과 고별을 했다고 가정하는 것이죠. 이렇게 계속헤서 BFS로 탐색을 진행하다보면 맵에는 화염으로 꽉차고 테스트케이스에 따라서 용사는 도착하지 못할 수도 있을 수도 있습니다.

위와같은 조건들을 고려하여 대충 구조는 아래와 같습니다.

[ 코드 ]

용사위치큐.add(용사위치)

불위치큐.add(불위치)

loop : while(!용사위치큐.isEmpty()){

while(!용사위치큐.isEmpty()) { // 용사 BFS 탐색

용사위치 = 용사위치큐.poll();

// 현재 용사 위치가 불이 난 경우 제외

if(map[이동위치.y][이동위치.x] != '*' ) continue;

for(방향 in 상하좌우) {

이동위치 = 용사위치.move(방향)

// 앞으로 이동할 곳이 빈 곳일 때

if(map[이동위치.y][이동위치 .x] == '.')

용사위치큐.add(이동위치);

}

}

while : 불위치  BFS 탐색

... 위와같은 패턴으로

}

[ 이하 구현 for Java ]

package org.prudy.study.algorithm.bfs;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class EscapeInFire {
    public static Scanner sc = new Scanner(System.in);
    public static int HEIGHT = sc.nextInt(), WIDTH = sc.nextInt();
    public static Coordinate[] directions = {new Coordinate(0, 1), new Coordinate(1, 0), new Coordinate(0, -1), new Coordinate(-1, 0)};
    public static Coordinate result;
    public static class Coordinate {
        int x, y, cost;
        
        /**
         * New Constructor
         * @param y
         * @param x
         */
        public Coordinate (int y, int x){
            this.x = x;
            this.y = y;
        }
        
        /**
         * New Constructor
         * @param y
         * @param x
         * @param cost
         */
        public Coordinate (int y, int x, int cost){
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
        
        /**
         * Add direction values and create a object
         * @param direction
         * @return new Coordinate Instance
         */
        public Coordinate move (Coordinate direction){
            return new Coordinate(y + direction.y, x + direction.x, this.cost+1);
        }
        
        
        /**
         * Check available coordinate
         * @return Boolean
         */
        public boolean isAvailable(){
            return this.y >= 0 && this.y < HEIGHT && this.x >= 0 && this.x < WIDTH;
        }
    }
    
    
    public static void main(String[] args) {
        
        /************************************************************************
         * 1. Define Field
         ************************************************************************/
        char[][] map = new char[HEIGHT][WIDTH];
        Queue<Coordinate> fires = new LinkedList<>();
        Queue<Coordinate> routes = new LinkedList<>();
        
        
        /************************************************************************
         * 2. Input Field
         ************************************************************************/
        for(int i = 0 ; i < HEIGHT ; i++){
            String row = sc.next();
            for(int j = 0 ;  j < WIDTH ; j++){
                map[i][j] = row.charAt(j);
                switch (map[i][j]) {
                case '*': fires.add(new Coordinate(i, j)); break;
                case 'S': routes.add(new Coordinate(i, j)); break;
                }
            }
        }
        
        
        /************************************************************************
         * 3. Process Field
         ************************************************************************/
        search : while (routes.size() > 0){
            
            Queue<Coordinate> newFires = new LinkedList<>();
            Queue<Coordinate> newRoutes = new LinkedList<>();
            
            // Heros's BFS
            while (routes.size() > 0){
                Coordinate route = routes.poll();
                if (map[route.y][route.x] == '*') continue;
                    
                for(Coordinate direction : directions){
                    Coordinate newRoute = route.move(direction);
                    if(!newRoute.isAvailable()) continue;
                    switch (map[newRoute.y][newRoute.x]) {
                    case '.':
                        newRoutes.add(newRoute);
                        map[newRoute.y][newRoute.x] = 'M';
                        break;
                    case 'D':    // 도착했을 경우
                        result = newRoute;
                        break search;
                    }
                }
            }
            
            // Fires's BFS
            while (fires.size() > 0){
                Coordinate fire = fires.poll();
                for(Coordinate direction : directions){
                    Coordinate newFire = fire.move(direction);
                    if(!newFire.isAvailable()) continue;
                    char target = map[newFire.y][newFire.x];
                    if(target != 'D' && target != 'X' && target != '*') {
                        newFires.add(newFire);
                        map[newFire.y][newFire.x] = '*';
                    }
                }
            }
            
            // For searching next level
            fires = newFires;
            routes = newRoutes;
        }
        
        /************************************************************************
         * 4. Result Field
         ************************************************************************/
        System.out.println(result != null ? result.cost: "impossible");
    }
}