노누리·2022년 9월 29일
0

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

  • '.': 빈 공간
  • '#': 벽
  • '@': 상근이의 시작 위치
  • '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

예제 입력 1

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

예제 출력 1

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ5427 {
    static boolean[][] visited;
    static char[][] map;
    static int[][] moves={{1,0},{-1,0},{0,1},{0,-1}};
    static int w,h;

    public static class Point{
        int x,y,time;
        boolean flag;

        public Point(int x, int y, int time,boolean flag) {
            this.x = x;
            this.y = y;
            this.time = time;
            this.flag=flag;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();

        int T=Integer.parseInt(br.readLine());

        for(int t=0;t<T;t++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            w=Integer.parseInt(st.nextToken());
            h=Integer.parseInt(st.nextToken());

            map=new char[h][w];
            visited=new boolean[h][w];

            for(int i=0;i<h;i++){
                map[i]=br.readLine().toCharArray();
            }

            int x=0;
            int y=0;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(map[i][j]=='@'){
                        x=i;
                        y=j;
                    }
                }
            }

            int result=bfs(x,y);

            if(result!=-1){
                sb.append(result+"\n");
            }else{
                sb.append("IMPOSSIBLE\n");
            }

        }

        System.out.print(sb);
    }

    private static int bfs(int i, int j) {
        Queue<Point> queue=new ArrayDeque<>();

        for(int x=0;x<h;x++){
            for(int y=0;y<w;y++){
                if(map[x][y]=='*'){
                    queue.offer(new Point(x,y,0,true));
                }
            }
        }
        queue.offer(new Point(i,j,0,false));

        while(!queue.isEmpty()) {
            Point p=queue.poll();

            if(!p.flag) {
                visited[p.x][p.y] = true;

                for (int d = 0; d < 4; d++) {
                    int a = p.x + moves[d][0];
                    int b = p.y + moves[d][1];

                    if (a < 0 || a >= h || b < 0 || b >= w) {
                        return p.time + 1;
                    }

                    if (!visited[a][b] && map[a][b] == '.') {
                        map[a][b]='@';
                        map[p.x][p.y]='.';
                        queue.offer(new Point(a, b, p.time + 1,false));
                    }
                }
            }

            //불 옮겨붙기
            else{
                for(int d=0;d<4;d++){
                    int a = p.x + moves[d][0];
                    int b = p.y + moves[d][1];

                    if (a < 0 || a >= h || b < 0 || b >= w) continue;

                    if(map[a][b]=='.' || map[a][b]=='@'){
                        map[a][b]='*';
                        queue.offer(new Point(a,b,p.time+1,true));
                    }
                }
            }
        }

        return -1;
    }
}

BFS 탐색을 이용하여 풀 수 있었지만 약간의 응용이 필요한 문제였다.

우선, 상근이가 건물을 탈출할 수 있는 경로를 찾아야했고, 불 또한 상하좌우로 옮겨붙어야했다.

Queue에 상근이의 위치정보와 불의 위치정보를 모두 넣어 상하좌우로 이동시켜주면서 상근이가 탈출한 시간을 반환해주면 된다.


좌표값 class 생성

public static class Point{
    int x,y,time;
    boolean flag;

    public Point(int x, int y, int time,boolean flag) {
        this.x = x;
        this.y = y;
        this.time = time;
        this.flag=flag;
    }
}

x 좌표값과 y 좌표값, 시간값과 boolean 값을 넣어주는데 이때 flag 값은 상근이인지 불인지 체크하기 위해 넣어주는 변수이다.


불의 확산

Queue<Point> queue=new ArrayDeque<>();

for(int x=0;x<h;x++){
    for(int y=0;y<w;y++){
        if(map[x][y]=='*'){
            queue.offer(new Point(x,y,0,true));
        }
    }
}

...

//불 옮겨붙기
if(p.flag){
    for(int d=0;d<4;d++){
        int a = p.x + moves[d][0];
        int b = p.y + moves[d][1];
        
        if (a < 0 || a >= h || b < 0 || b >= w) continue;
        
        if(map[a][b]=='.' || map[a][b]=='@'){
            map[a][b]='*';
            queue.offer(new Point(a,b,p.time+1,true));
        }
    }
}

map에 들어있는 불의 위치값을 모두 queue에 넣어준다.

queue에서 poll한 값의 flag가 true인지 체크한뒤 상하좌우로 불을 퍼트려준다.

이때, 건물벽인 경우에는 불이 퍼지지 않기 때문에 빈 공간이거나 상근이가 있는 위치라면 불이 퍼질 수 있다.

불이 퍼진 뒤에는 map에 불이 옮겨붙었다는 표시를 해주고 queue에 다음 불의 위치를 저장해준다.


상근이의 이동

queue.offer(new Point(i,j,0,false));

while(!queue.isEmpty()){
    Point p=queue.poll();
    
    if(!p.flag){
        visited[p.x][p.y]=true;
        
        for(int d=0;d< 4;d++){
            int a=p.x+moves[d][0];
            int b=p.y+moves[d][1];
            
            if(a< 0||a>=h||b< 0||b>=w){
                return p.time+1;
            }
            
            if(!visited[a][b]&&map[a][b]=='.'){
                map[a][b]='@';
                map[p.x][p.y]='.';
                queue.offer(new Point(a,b,p.time+1,false));
            }
        }
    }
}

평소 아는 BFS 탐색의 방식을 이용하면 쉽게 구현할 수 있는 부분이다. 유의할 점은 상하좌우에 불이나 건물벽이 존재하지 않으면 이동할 수 있다는 것이다.

다만 map의 바깥으로 빠져나갔을 때는 다른 BFS 문제와 달리 탈출에 성공했다는 뜻이기 때문에 시간+1 값을 반환해준다.

그것이 아니라면 상근이가 이동했다는 뜻이므로 map의 @, . 값을 갱신해준다.

이후 이동한 좌표값을 큐에 넣어 이 작업을 반복해준다.


주의할 점

순서대로 작업을 진행하면 정답을 맞출 수 있는데 이때 주의해야할 점은 BFS 탐색시 상근이의 위치값을 먼저 큐에 담았을 때, 불이 퍼지기 전에 상근이가 먼저 이동하는 순서가 되어버리기 때문에

사실은 상근이가 이동하지 못하는 경우에도 이동할 수 있게된다.

이 사실을 주의해서 불의 위치값을 먼저 큐에 담아주면 불이 먼저 퍼진 후 상근이가 이동하게 되기 때문에 정답이 나올 수 있게된다.

profile
백엔드 개발자입니다.

0개의 댓글