[JAVA]불!(Baekjoon)

문제

문제

 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

 불은 각 지점에서 네 방향으로 확산된다.

 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

 지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

 다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

 각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

 J는 입력에서 하나만 주어진다.

출력

 지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

 지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

 

예제 입력 1

4 4
####
#JF#
#..#
#..#

예제 출력 1

3

풀이

 이 문제는 풀다가 전혀 감이 안와서 풀이를 찾아보았다.
 처음에 접근방식은 그냥 배열만 사용하는 방법과 노드 클래스를 만들어 J, F, . 을 구분하여 생성하고 진행하는 방식으로 고려해보았으나, 모르겠었다.

 찾아본 방법은 아래와 같다.

 처음에 이차원 char배열에 입력 및 할당을 한다. 그리고 입력값이 J 혹은 F일 경우 각각, PersonQ와 FireQ라는 Queue에 좌표값을 이용해 노드를 삽입한다.
 그리고 반복문을 통해 진행하는데, 우선 FireQ에 존재하는 불의 좌표들을 내부 반복문을 통해 모두 꺼내어 상하좌우로 번지게 한 다음(배열값 변경), 그 번진 불들의 좌표를 큐에다가 삽입한다. 내부 반복문은 현재 시각에서의 큐의 크기만큼만 반복된다. 현재 페이즈에 번진 불들은 다음 페이즈에 번지는 근원이 되어야 하기 때문에 큐에 존재해야한다.
 그 다음, PersonQ에 존재하는 사람의 좌표들을 내부 반복문을 통해 모두 꺼내어 상하좌우로 이동시킨다. 불 혹은 벽이라면 이동불가이고, 이동이 가능한 경우에만 큐에 삽입한다. 이 또한, 불과 마찬가지로 현재 시각에서의 큐의 크기만큼만 반복된다. 이 때, 배열의 사이즈를 벗어난, 즉 탈출에 성공한 경우에 시각을 리턴하며 반복문을 종료시킨다. 반대로 큐의 사이즈가 0이 되어 더이상 이동가능한 사람이 존재하지 않는다면, 탈출실패로 처리된다.

import java.io.*;
import java.util.*;

public class _4179 {
    static int r,c;
    static char[][] map;    //좌표값 배열
    static Queue<int[]> fireQ, personQ; //불과 사람 각각의 큐
    static int[] dx = {-1, 1, 0, 0};    //x로의 이동방향
    static int[] dy = {0, 0, -1, 1};    //y로의 이동방향
    public static void main(String[] args) throws IOException{
        //입력 및 할당, 큐에 삽입
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        map = new char[r][c];
        String line;
        fireQ = new LinkedList<>();
        personQ = new LinkedList<>();
        for(int i=0; i<r; i++) {
            line = br.readLine();
            for(int j=0; j<c; j++) {
                map[i][j] = line.charAt(j);
                if(map[i][j] == 'J') {
                    personQ.add(new int[] {j,i,0});
                }else if(map[i][j] == 'F') {
                    fireQ.add(new int[] {j,i});
                }
            }
        }
        //반복문 진행
        int res = -1;
        out: while(true) {
            //불 번져나감
            int fSize = fireQ.size();   //현재 페이즈에서 불 개수
            for(int i=0; i<fSize; i++) {
                int[] p = fireQ.poll();
                fireMoving(p[0], p[1]);
            }
            //사람 이동
            int pSize = personQ.size(); //현재 페이즈에서 사람 수
            for(int i=0; i<pSize; i++) {
                int[] p = personQ.poll();
                res = escape(p[0], p[1], p[2]);
                if(res != -1) break out;    //탈출에 성공한 경우
            }
            if(personQ.isEmpty()) break;    //탈출에 실패한 경우
        }

        if(res == -1)
            System.out.println("IMPOSSIBLE");
        else
            System.out.println(res);
    }
    //사람 이동 함수
    static int escape(int x, int y, int time) {
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            //탈출에 성공한 경우
            if(nx<0 || ny<0 ||  nx>c-1 || ny>r-1)
                return time+1;
            //벽이라면 이동한 후 큐에 좌표 삽입
            if(map[ny][nx] == '.') {
                map[ny][nx] = 'J';
                personQ.add(new int[] {nx, ny, time+1});
            }
        }
        return -1;
    }
    //불 번짐 함수
    static void fireMoving(int x, int y) {
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            //범위 밖이라면 continue
            if(nx < 0 || ny < 0 || nx > c-1 || ny > r-1) continue;
            //빈 방 혹은 사람이 있다면 불이 번짐, 큐에 좌표 삽입
            if(map[ny][nx] == '.' || map[ny][nx] == 'J') {
                map[ny][nx] = 'F';
                fireQ.add(new int[] {nx, ny});
            }
        }
    }
}

고찰

 본 문제를 보고 게임같다는 생각을 했다. 그래서 객체지향기법으로 풀어보려고 했으나 너무 어렵게 생각한 것 같다. 배열을 반복문을 통해 초기화시키며 풀면 위의 풀이와 같이 직관적이고 효율적으로 짤 수 있었다.
공부할게 많이 남은것 같다. 파이팅!