링크

링크텍스트

문제

풀이

bfs를 활용하여 풀었다.

먼저 불을 이동하고 지훈이를 이동시켰다.

불과 지훈이를 같은 이차원 배열에 넣으면 지훈이가 탈출할때의 시간을 처리하기 까다로워서
불의 이동은 matrix라는 배열에, 지훈이의 이동은 visited라는 배열에 시간을 저장했다.

그리고 만약에 벽쪽에 도달했으면 그 값들을 hashset에 넣어서 최솟값 + 1을 수행해 최소 시간을 저장했다. set이 비어있으면 impossible

이해가 안된다면 sysout의 주석들을 풀어서 이동하는 흐름을 보면 이해하기 쉽다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node{
    int x;
    int y;
    String type;
    int value;

    public Node(int x, int y, String type) {
        this.x = x;
        this.y = y;
        this.type = type;
    }
}

public class Algorithm {
    public static String[][] matrix;
    public static int[] dx = new int[]{-1, 0, 1, 0};
    public static int[] dy = new int[]{0, 1, 0, -1};
    public static int[][] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = br.readLine().split(" ");
        int r = Integer.parseInt(arr[0]);
        int c = Integer.parseInt(arr[1]);

        matrix = new String[r][c];
        visited = new int[r][c];

        int jihunX = 0;
        int jihunY = 0;

        //불먼저 bfs하고 지훈이가 불이 없는 쪽으로 이동
        Queue<Node> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();

        for(int i=0;i<r;i++){
            arr = br.readLine().split("");

            for(int j=0;j<arr.length;j++){
                matrix[i][j] = arr[j];

                //벽인 경우 -1로 초기화
                if(matrix[i][j].equals("#")){
                    visited[i][j] = -1;
                }

                if(matrix[i][j].equals("J")){
                    if(i == 0 || i == (matrix.length - 1) || j == 0 || j == (matrix[0].length - 1)){
                        set.add(0);
                    }

                    jihunX = i;
                    jihunY = j;
                }

                if(matrix[i][j].equals("F")){
                    queue.add(new Node(i, j, "F"));
                    visited[i][j] = -1;
                }
            }
        }

        queue.add(new Node(jihunX, jihunY, "J"));

//        for(int i=0;i<matrix.length;i++){
//            System.out.println(Arrays.toString(matrix[i]));
//        }
//
//        System.out.println("------------------------------------");


        while(!queue.isEmpty()){
            Node currentNode = queue.poll();

            int x = currentNode.x;
            int y = currentNode.y;
            String type = currentNode.type;

            //현재꺼낸게 불인경우
            if(type.equals("F")){
                System.out.println("fire");

                for(int i=0;i<4;i++){
                    int newX = x + dx[i];
                    int newY = y + dy[i];

                    // 배열 넘어간 경우
                    if(newX < 0 || newY < 0 || newX >= matrix.length || newY >= matrix[0].length) continue;

                    // 벽인경우
                    if(matrix[newX][newY].equals("#") || matrix[newX][newY].equals("F")) continue;

                    matrix[newX][newY] = "F";

                    queue.add(new Node(newX, newY, "F"));

                }

//                for(int i=0;i<matrix.length;i++){
//                    System.out.println(Arrays.toString(matrix[i]));
//                }
//
//                System.out.println("------------------------------------");

            }
            //지훈이인 경우
            else{
                System.out.println("ji");

                for(int i=0;i<4;i++){
                    int newX = x + dx[i];
                    int newY = y + dy[i];

                    // 배열 넘어간 경우
                    if(newX < 0 || newY < 0 || newX >= matrix.length || newY >= matrix[0].length) continue;

                    //벽이거나 불인경우
                    if(matrix[newX][newY].equals("#") || matrix[newX][newY].equals("F") || visited[newX][newY] != 0) continue;

                    queue.add(new Node(newX, newY, "J"));
                    visited[newX][newY] = visited[x][y] + 1;

                    //탈출조건
                    if(newX == 0 || newX == (matrix.length - 1) || newY == 0 || newY == (matrix[0].length - 1)){
                        set.add(visited[newX][newY]);
                    }

                }

//                for(int i=0;i<matrix.length;i++){
//                    System.out.println(Arrays.toString(visited[i]));
//                }
//                System.out.println("-------------------");
            }



        }

//        for(int i=0;i<matrix.length;i++){
//            System.out.println(Arrays.toString(matrix[i]));
//        }
//
//        System.out.println("------------------------------------");
//
//        for(int i=0;i<visited.length;i++){
//            System.out.println(Arrays.toString(visited[i]));
//        }

        if(!set.isEmpty()){
//            System.out.println("탈출");

            int answer = Integer.MAX_VALUE;
            for(Integer element : set){
                answer = Math.min(answer, element);
            }

            System.out.println((answer+1));

        } else{
            System.out.println("IMPOSSIBLE");
        }








    }
}