[백준 5427] 불 (JAVA)

백준(BOJ) 5427 불

 

난이도
221226 기준 골드 4

사용 알고리즘
BFS

문제 링크
https://www.acmicpc.net/problem/5427

5427번: 불

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

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

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

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

 

 

입력

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

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

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

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

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

 

출력

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

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 빌딩을 탈출하는데 가장 빠른시간을 구하고 빌딩을 탈출 할 수 없는 경우 IMPOSSIBLE을 출력한다. 보자마자 bfs로 풀어야겠다는 감이 오네요

 

3. 풀이 구상

 

 풀이 자체는 어렵지 않은데 한가지 걱정되는 것은 테스트케이스가 100개가 된다는 것입니다. w,h의 최대인 1000에 테케 100개면 bfs를 돌렸을때1000*1000*100 = 100,000,000 약 1억번의 연산이 나올 수 도 있는데 시간초과 기준이 1초이니 애매하긴 합니다. 일단은 무난하게 한번 풀어보고 시간초과가 뜨면 시간을 줄일 방법이 있는지 확인 해보겠습니다.

 출구가 어디인지 딱 정해진건 아니기에 r,c 범위를 벗어나면 출구로 도착하는 것만 확인하면 되겠습니다.

 

 

4. 코드 작성

 

1. 정답 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int T;
    static int H, W;
    static char[][] building;
    static Queue<RC> q;
    static RC SangGeun;
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    static int result;

    static class RC {
        int r;
        int c;

        int isfire;

        public RC(int r, int c, int isfire) {
            this.r = r;
            this.c = c;
            this.isfire = isfire;

        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for(int tc = 0; tc < T; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            W = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());
            building = new char[H][W];
            q = new LinkedList<>();
            result = -1;

            SangGeun = new RC(-1,-1,0);

            for (int r = 0; r < H; r++){
                String str = br.readLine();
                for(int c = 0; c < W; c++){
                    char cur = str.charAt(c);
                    building[r][c] = cur;
                    if(cur == '*'){
                        q.add(new RC(r,c,1));
                    } else if(cur=='@'){
                        SangGeun.r = r;
                        SangGeun.c = c;
                    }
                }
            }
            q.add(SangGeun);
            
            boolean isPossible = bfs();
            if(isPossible){
                bw.write(result+"\n");
            } else {
                bw.write("IMPOSSIBLE\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();

    }

    static boolean bfs() {
        int step[][] = new int[H][W];

        step[SangGeun.r][SangGeun.c] = 1;

        while(q.size()>0){
            RC cur = q.poll();

            int curr = cur.r;
            int curc = cur.c;
            int isfire = cur.isfire;

            for(int d = 0; d < 4; d++){
                int nr = curr + dr[d];
                int nc = curc + dc[d];

                if(isfire==1){
                    if(nr>=0 && nr < H && nc >= 0 && nc < W){
                        if(building[nr][nc]=='.' && step[nr][nc]==0){
                           step[nr][nc]=-1;
                           q.add(new RC(nr,nc,1));
                        }
                    }
                } else if(isfire==0){
                    if(nr>=0 && nr < H && nc >= 0 && nc < W){
                        if(building[nr][nc]=='.' && step[nr][nc]==0){
                           step[nr][nc] = (step[curr][curc]+1);
                           q.add(new RC(nr,nc, 0));
                        }
                    } else {
                       result = step[curr][curc];
                       return true;
                    }
                }
            }
        }

        return false;
    }

}

 

2. 주의할 점

 

 한 번에 정답을 맞췄습니다. 문제의 포인트는 Queue에 불을 모두 넣어두고 상근이를 마지막에 넣어줘야 하는 것입니다. 나머지는 일반적인 bfs 문제 처럼 푸시면 됩니다.

 

 

---

풀이 후기

 IDE를 이클립스에서 인텔리제이로 바꾸고 처음 알고리즘 문제를 풀어봤는데 단축키 적응하는데 조금 시간이 걸리겠네요.  여담이지만 오늘부터 SSAFY 2학기가 사실상 시작되고 팀빌딩까지 마쳤는데요 첫날부터 과제도 있고 확실히 2학기는 1학기와 완전히 다른 마음가짐으로 임해야겠네요 바빠지더라도 1일 1알고리즘 포스트는 놓지 않도록 해보겠습니다.