[백준 4179번] 불!

난이도: 골드 IV

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

4179번: 불!

참고한 글:

• BOJ 질문 게시판의 반례 모음 https://www.acmicpc.net/board/view/31494
• leeinae 님의 블로그 글 https://velog.io/@leeinae/Algorithm-%EB%B0%B1%EC%A4%80-4179-%EB%B6%88-java

Java 피지컬 늘리기 목적으로 풀어 본 문제입니다.

쉽게 생각하고 접근했다가 Java에서 메소드와 파라미터에 관한 의문점도 하나 찾아내고...

 

기본적으로는 BFS를 이용한 문제입니다.

다만 특이한 점은 맵에 불이 있고, 이 불이 매 시간마다 상하좌우로 퍼집니다.

불에 닿지 않고, 벽에 막히지 않은 가장자리에 도달할 수 있다면 탈출 성공입니다.

 

포인트는  큐에 불을 지훈이보다 먼저 넣는 것입니다. 같은 시간에 불과 지훈이가 같은 좌표로 이동할 수 없기 때문에, 불이 먼저 위치를 선점하고, 지훈이는 이에 따라 이동할 수 없는 좌표로 고려하도록 하는 것입니다.

 

문제가 어려운 문제는 아니었지만 Java 문법에 적응하기에는 매우 괜찮은 문제였던 것 같습니다.

 

채점 결과

처음에 시도했다가 실패한 코드

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static class Node {
        int x, y;
        char[][] board;
        Node (int x, int y, char[][] board) {
            this.x = x;
            this.y = y;
            this.board = board;
        }
    }

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

    //문제를 위한 기본 변수
    static int r, c;
    static final int MAX_R = 1000;
    static final int INF = 999999999;
    static int[][] visited = new int[MAX_R][MAX_R];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int jx, jy;  //지훈이가 현재 위치한 장소
    static int answer = INF;  //탈출할 수 있는 가장 가까운 거리


    static boolean hasEscaped (int x, int y) {
        if (x < 0 || x >= r || y < 0 || y >= c) return true;
        else return false;
    }

    static boolean inBoundary(int x, int y) {
        if (x >= 0 && x < r && y >= 0 && y < c) return true;
        else return false;
    }

    static char[][] fire_spread(char[][] boardInput) {
        //불이 전이될 장소 목록
        Queue<Coord> q = new LinkedList<>();

        char[][] boardOutput = boardInput;

        //현재 상하좌우에 불이 있는 곳을 찾는다.
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                //current = board[i][j]
                //현재 위치한 곳이 빈 공간이 아니라면 신경쓰지 않아도 된다.
                if (boardOutput[i][j] != '.') continue;
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    //불이 판 밖에 나는 경우는 없다.
                    if (!inBoundary(nx, ny)) continue;
                    //현재 위치한 곳의 옆에 불이 나 있는 경우
                    if (boardOutput[nx][ny] == 'F') {
                        q.add(new Coord(i, j));
                        break;
                    }
                }
            }
        }

        //기록한 불 붙기 후보 좌표에 불을 붙인다.
        while(!q.isEmpty()) {
            Coord next = q.poll();
            boardOutput[next.x][next.y] = 'F';
        }

        return boardOutput;
    }

    public static void main(String[] args) {
        //기본 입력 받기
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt(); c = sc.nextInt();
        char[][] boardIn = new char[MAX_R][MAX_R];
        for (int i = 0; i < r; i++) {
            String temp = sc.next();
            for (int j = 0; j < c; j++) {
                boardIn[i][j] = temp.charAt(j);
                //지훈이의 위치 찾기
                if (boardIn[i][j] == 'J') {
                    boardIn[i][j] = '.';
                    jx = i; jy = j;
                }
            }
        }

        //visited 배열 초기화
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (i == jx && j == jy) visited[i][j] = 0;
                else visited[i][j] = INF;
            }
        }

        /*
        1. 일단 불을 상하좌우 한 칸씩 붙이고 (이때 지훈이가 있는 곳이어도 상관없다),
        2. 지훈이가 이동할 수 있는 곳을 찾는다.
        3. 그 중 탈출할 수 있는 곳이 있으면 지금까지의 이동값을 정답에 기록한다.
         */

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(jx, jy, boardIn));

        while(!q.isEmpty()) {
            Node next = q.poll();
            //기존의 board로부터 상하좌우 불을 하나씩 붙이고,
            char[][] next_board = next.board;
            fire_spread(next_board);

            //bfs를 이용하여 지훈이가 이동할 수 있는 곳을 찾는다.
            for (int dir = 0; dir < 4; dir++) {
                int nx = next.x + dx[dir];
                int ny = next.y + dy[dir];
                //그 중 탈출할 수 있는 곳이 있으면 지금까지의 이동값을 정답에 기록한다.
                if (hasEscaped(nx, ny)) {
                    answer = Math.min(answer, visited[next.x][next.y] + 1);
                    continue;
                }
                if (next_board[nx][ny] == '#' || next_board[nx][ny] == 'F') continue;

                //디버깅
                System.out.println("current start: " + next.x + ", " + next.y);
                System.out.println("moving to: " + nx + ", " + ny);
                for (int i = 0; i < r; i++) {
                    for (int j = 0; j < c; j++) {
                        System.out.print(next_board[i][j] + " " );
                    }
                    System.out.println();
                }
                System.out.println();

                if (visited[nx][ny] > visited[next.x][next.y] + 1) {
                    visited[nx][ny] = visited[next.x][next.y] + 1;
                    System.out.println("------");
                    System.out.println("adding: from " + next.x + ", " + next.y);
                    System.out.println("to: " + nx + ", " + ny);
                    System.out.println("board:");
                    for (int i = 0; i < r; i++) {
                        for (int j = 0; j < c; j++) {
                            System.out.print(next_board[i][j] + " " );
                        }
                        System.out.println();
                    }
                    System.out.println("------");
                    q.add(new Node(nx, ny, next_board));
                }
            }
        }

        if (answer == INF) System.out.println("IMPOSSIBLE");
        else System.out.println(answer);
    }
}