[백준 알고리즘] 5427번 자바(Java) 불

문제

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

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

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

 

입력

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

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

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

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

출력

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

 

풀이

• 시간 복잡도, 공간 복잡도
  • 테스트 케이스가 100개이다 따라서 매 케이스는 100만 복잡도 이내로 이루어져야한다
  • 너비*높이의 최대는 100만이므로 전체를 한번씩만 방문하도록 짜야한다(BFS)
    • 그리고 다 방문할 필요가 없기에 시간복잡도는 문제가 없다
  • 메모리 256MB 약 6000~7000만개, 크게 문제없어보인다
• 처음 시도
  • Node 에 파라미터 h,w,cnt 를 뒀다 → 메모리 초과
  • 불은 2개 이상일 수 있다
  • 불이 옮길 자리는 상근이가 갈 수 없다 = 불이 상근이보다 턴이 항상 빠르다
  • 매번 불 큐와 상근이 큐의 peek.cnt를 비교해서 (불 cnt>상근 cnt)일때만 상근이 BFS가 작동하도록 했다
• 수정 과정
  • Node에 cnt파라미터를 제외하고 턴이 돌때마다 각 큐의 size를 재서 반복문을 돌리는 과정으로 수정했다. → cnt파라미터없더라도 턴 가능, 메모리초과 해결(위에 밑줄 2개 해결)

 

 

 

 

 

예제 입력 예시

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

 

예제 출력 예시

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

 

소스코드

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

//5427번 불
//0번 벽, 1번 빈공간, 2번 상근, 3번 불
//참고로 불은 2개이상 가능

public class Main{

    private static int h;
    private static int w;

    static class Node{
        int y, x;
        public Node(int y, int x){
            this.y = y;
            this.x = x;
        }
    }

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

        int[][] xy = {{0,-1},{1,0},{0,1},{-1,0}};
        char[][] map;
        boolean[][] visited;
        boolean possible;
        int cnt;
        Queue<Node> fireNodes;
        Queue<Node> moveNodes;

        while(T>0){
            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];

            fireNodes = new LinkedList<>();
            moveNodes = new LinkedList<>();


            //대입
            for (int i = 0; i < h; i++) {
                String line = br.readLine();
                for (int j = 0; j < w; j++) {
                    map[i][j] = line.charAt(j);
                    if(map[i][j] == '@') moveNodes.add(new Node(i,j));
                    else if(map[i][j] == '*') fireNodes.add(new Node(i,j));
                }
            }

            possible = false;
            cnt = 0;
            escape:while(!moveNodes.isEmpty()){
                cnt++;
                //불먼저
                int size = fireNodes.size();
                for (int i = 0; i < size; i++) {
                    Node curFireNode = fireNodes.poll();
                    for (int j = 0; j < 4; j++) {
                        int curY = curFireNode.y+xy[j][0];
                        int curX = curFireNode.x+xy[j][1];
                        if(range(curY, curX)&&(map[curY][curX] == '.'||map[curY][curX] =='@')){
                            fireNodes.add(new Node(curY, curX));
                            map[curY][curX] = '*';
                        }
                    }
                }

                //상근이 턴
                size = moveNodes.size();
                for (int i = 0; i < size; i++) {
                    Node curMoveNode = moveNodes.poll();

                    for (int j = 0; j < 4; j++) {
                        int curY = curMoveNode.y+xy[j][0];
                        int curX = curMoveNode.x+xy[j][1];
                        if(curY<0||curX<0||curY>=h||curX>=w){
                            sb.append(cnt).append("\n");
                            possible = true;
                            break escape;
                        }
                        else if(!visited[curY][curX]&&map[curY][curX] == '.'){
                            moveNodes.add(new Node(curY, curX));
                            visited[curY][curX] = true;
                        }
                    }
                }
            }

            if(!possible) sb.append("IMPOSSIBLE").append("\n");
            T--;
        }
        System.out.println(sb);
    }

    public static boolean range(int y, int x){
        return y>=0 && x >=0 && y<h && x<w;
    }
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/5427

5427번: 불