[백준] bfs - 5427번 불 (Java)

문제링크

5427번: 불

 

접근한 방법

• 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다.

 

---

풀이방법

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.

 

불이 번지는 것도 고려해야하므로, 불의 시작지점부터 BFS를 수행한다.

불이 번지는 동작이 수행되었으면 그 이후로

시작지점(상범이가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.
특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

 

---

소스코드 작성 방법

• 맵의 크기(h, w)을 전역 필드로 선언한다.
• 맵의 정보(map), 방문 여부 및 거리(visited)도 전역 필드로 선언한다.
• 상범이의 처음 위치(sangR, sangC)와 탈출가능할 때 마지막 위치(endR, endC)를 전역 필드로 선언한다.
• 방향 배열 dr, dc로 상 좌 하 우 움직임을 저장한다.
• 탈출 성공 여부(isSuccess)를 전역 필드로 선언한다.
• 불의 위치를 담는 큐(fireQ)와 상범이의 위치(sangQ)를 담는 큐를 전역 필드로 선언한다.
• 행과 열의 index를 저장할 수 있는 클래스를 선언한다.

 

• 주의사항 1 (입력받을 때)
• bfs를 수행하기 전에 map, visited, queue를 반드시 초기화해준다.
• * 문자를 만날 때마다 불의 위치를 담는 큐에 좌표 객체를 넣어준다.
• @ 문자를 만나면 상범이의 위치를 선언하였던 전역 필드에 넣어준다.
• visited 배열을 -1로 초기화해준다.

 

• bfs 메소드를 선언하여 아래와 같이 처리해준다.
• 큐에 맨 처음 상범이 좌표의 객체를 넣어준다.
• 처음 칸도 지나는 것에 포함되므로 visited[sangR][sangC] = 0 으로 처리해주어, 방문 처리 및 거리를 저장한다.
• 주의사항 2
• 상범이가 시작위치부터 탈출가능한 위치에 있을 때를 처리해준다.
  
  
• while문으로 불의 위치를 담은 큐나 상범이의 위치를 담은 큐에 남아있는 게 없을 때까지 탐색을 수행한다.
• 불의 위치를 담은 큐와 상범이의 위치를 담은 큐를 나누어서 다음과 같이 수행한다.
• 나누어서 수행을 해야하므로, 불의 위치를 담은 큐의 크기만큼 불이 번지는 과정을 먼저 수행한다.
  • fireQ.poll()로 큐에서 좌표 객체를 꺼내 현재 좌표인 fireCurR, fireCurC 필드에 저장한다.
  • 반복문으로 현재 좌표에서 4방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 맵의 크기를 벗어나거나 이미 불이 있거나(*) 벽이어서(#) 진행하지 못할 시 continue로 넘어간다.
  • 맵의 값이 '.'이고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) 불이 지나간 자리를 불로 표시하고 불의 위치를 담은 큐에 다음 좌표의 객체를 넣어준다.
• 다음은 상범이의 위치를 담은 큐의 크기만큼 상범이가 빠져나갈 수 있는 과정을 탐색한다.
  • sangQ.poll()로 큐에서 좌표 객체를 꺼내 현재 좌표인 sangCurR, sangCurC 필드에 저장한다.
  • 상범이가 지나간 위치를 '.'으로 변경한다.
  • 반복문으로 현재 좌표에서 4방향으로 탐색을 수행한다.
  • 이 때, 다음으로 탐색할 좌표가 탐색할 맵의 크기를 벗어나거나 이미 불이 있거나(*) 벽이어서(#) 진행하지 못할 시 continue로 넘어간다.
  • 다음으로 탐색할 좌표가 맵의 끝부분이고 진행 가능할 때 (.) isSuccess를 true로 처리하고 상범이의 다음 위치를 최종 좌표에 넣는다. 
  • 그리고 visited[sangNextR][sangNextC]에 visited[sangCurR][sangCurC] + 1을 저장한다. (현재까지의 칸 수 + 1)
    return으로 반복문을 빠져나온다.
  • 맵의 값이 '.'이고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) visited[sangNextR][sangNextC]에 visited[sangCurR][sangCurC] + 1을 저장하여 거리의 정보를 넣어준다. (현재까지의 칸 수 + 1)
    큐에 다음 좌표의 객체를 넣어준다.

 

예시) 더보기 클릭

 

 

 

---

실수한점

• 시작부터 탈출가능한 위치에 있을 때의 경우를 생각해주지 않았다.
• 불이 번질 때 불이 이미 있거나, 벽일 경우 예외 처리를 해주지 않았다.
• 불의 위치가 여러개일 수 있는데 불의 위치 하나만 큐에 넣었다 ㅠㅠ
  입력을 받을 때 * 문자를 만나면 그 때 그 때 큐에 넣어주어야함 !
  (이거 때문에..... 반례랑 예제는 다 맞는데 몇번을 틀렸는지...후....)

 

---

반례 참고

1
12 5
############
#.#....@..##
#....#.#...#
.#..##...##.
.#..#####.#.

답 : 8



1
4 3 
*###
#*.@
####

답 : 1



1
4 5
####
#*##
#...
#@##
#####

답 : IMPOSSIBLE



1
7 4
###.###
#.....#
#@....#
*######

답 : 5

 

소스코드

package baekjoon.dfs_bfs;
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q_5427_Fire_20210728 {
    public static int w,h; // h : 행 | w : 열
    public static char[][] map;
    public static int[][] visited;
    public static int sangR, sangC;
    public static int endR, endC;
    public static int[] dr = {-1,0,1,0};
    public static int[] dc = {0,-1,0,1};
    public static boolean isSuccess; // 탈출 성공 여부
    public static Queue<Pair> fireQ, sangQ;

    public static void bfs(){
        isSuccess = false;

        sangQ.add(new Pair(sangR, sangC)); // 상범이의 처음 위치 큐에 넣기

        visited[sangR][sangC] = 0; // 상범이의 현재 위치 방문 처리
        map[sangR][sangC] = '.'; // 상범이 지나간 위치를 . 으로 변경

        if(sangR == 0 || sangR == (h-1) || sangC == 0 || sangC == (w-1)) {
            isSuccess = true;
            // 상범위의 다음 위치를 최종 좌표에 넣기
            endR = sangR;
            endC = sangC;
            return;
        } else {

            while (!sangQ.isEmpty() || !fireQ.isEmpty()) {

                // 불의 이동
                int fireSize = fireQ.size();
                for (int fire = 0; fire < fireSize; fire++) {
                    Pair fireCur = fireQ.poll();

                    int fireCurR = fireCur.r;
                    int fireCurC = fireCur.c;

                    for (int i = 0; i < 4; i++) {

                        int fireNextR = fireCurR + dr[i];
                        int fireNextC = fireCurC + dc[i];

                        if (fireNextR < 0 || fireNextC < 0 || fireNextR >= h || fireNextC >= w) continue;
                        else if (map[fireNextR][fireNextC] == '*' || map[fireNextR][fireNextC] == '#') continue; // 이미 불이 번져있거나, 벽이면 건너뛰기
                        else if (map[fireNextR][fireNextC] == '.' || map[fireNextR][fireNextC] == '@') {
                            map[fireNextR][fireNextC] = '*'; // 불이 지나간 자리를 불로 표시
                            fireQ.add(new Pair(fireNextR, fireNextC));
                        }

                    }
                }

                // 상범이의 이동
                int sangSize = sangQ.size();
                for (int sangBum = 0; sangBum < sangSize; sangBum++) {
                    Pair sangCur = sangQ.poll();

                    int sangCurR = sangCur.r;
                    int sangCurC = sangCur.c;
                    map[sangCurR][sangCurC] = '.'; // 상범이 지나간 위치를 .으로 변경

                    for (int i = 0; i < 4; i++) {
                        int sangNextR = sangCurR + dr[i];
                        int sangNextC = sangCurC + dc[i];

                        if (sangNextR < 0 || sangNextC < 0 || sangNextR >= h || sangNextC >= w) continue;
                        else if (map[sangNextR][sangNextC] == '*' || map[sangNextR][sangNextC] == '#') continue;
                        // 상범이의 다음 위치가 맵의 끝에 있으며 이동 가능하면 탈출 성공
                        else if (sangNextR == 0 || sangNextR == (h - 1) || sangNextC == 0 || sangNextC == (w - 1)) {
                            if (map[sangNextR][sangNextC] == '.') {
                                isSuccess = true;
                                // 상범이의 다음 위치를 최종 좌표에 넣기
                                endR = sangNextR;
                                endC = sangNextC;
                                visited[sangNextR][sangNextC] = visited[sangCurR][sangCurC] + 1;
                                return; // break를 하지 말고 return을 해야 빠져나옴
                            } else continue;
                        }

                        else if (map[sangNextR][sangNextC] == '.' && visited[sangNextR][sangNextC] == -1) {
                            visited[sangNextR][sangNextC] = visited[sangCurR][sangCurC] + 1; // 거리 정보 넣기
                            map[sangNextR][sangNextC] = '@'; // 상범이 위치로 표시
                            sangQ.add(new Pair(sangNextR, sangNextC));
                        }
                    }
                }
            }
        }

    }

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

        int 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()); // 행
            map = new char[h][w];
            visited = new int[h][w];
            fireQ = new LinkedList<>();
            sangQ = new LinkedList<>();

            for (int i = 0; i < h; i++) {
                String temp = br.readLine();
                for (int j = 0; j < w; j++) {
                    map[i][j] = temp.charAt(j);
                    visited[i][j] = -1; // 초기화
                    if (map[i][j] == '*') {
                        fireQ.add(new Pair(i, j));// 불의 위치 큐에 넣기
                    }
                    if (map[i][j] == '@') {
                        sangR = i;
                        sangC = j;
                    }
                }
            }

            bfs();
            if(isSuccess){
                bw.write(visited[endR][endC]+1+"\n"); // 마지막 밖으로 나오는 시간을 1 더해준다
            } else {
                bw.write("IMPOSSIBLE\n");
            }
        }

        br.close();
        bw.close();
    }

    static class Pair{
        int r;
        int c;

        public Pair(int r, int c){
            this.r = r;
            this.c = c;
        }
    }

    // debug
    public static void write(int[][] map) {
        for(int i=0 ; i<h ; i++) {
            for(int j=0 ; j<w ; j++) {
                System.out.print(map[i][j]+",");
            }
            System.out.println();
        }
        System.out.println();
    }

}