[알고리즘] 백준 4179 불

www.acmicpc.net/problem/4179

4179번: 불!

지훈이는 매분 미로를 상하좌우로 한 칸씩 이동할 수 있다.

 

불도 매분 상하좌우로 퍼진다.

 

불을 피해서 지훈이는 미로를 탈출해야한다.

 

Queue를 두 개 사용한 방법과 한 개 사용한 방법 두가지고 구현했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_4179 {
    static int R;
    static int C;
    static int[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;

    static final int fire = -1;
    static final int wall = 0;
    static final int jihun = 1;
    static final int root = 2;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        visited = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            s = br.readLine();

            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '#') {
                    map[i][j] = wall;
                }
                else if (s.charAt(j) == 'J') {
                    map[i][j] = jihun;
                }
                else if (s.charAt(j) == 'F') {
                    map[i][j] = fire;
                }
                else {
                    map[i][j] = root;
                }
            }
        }

        bfs();
    }

    static void bfs() {
        Queue<Location> jihunQueue = new LinkedList<Location>();
        Queue<Location> fireQueue = new LinkedList<Location>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == fire) {
                    fireQueue.add(new Location(i, j, 0));
                    visited[i][j] = true;
                }
                else if (map[i][j] == jihun) {
                    jihunQueue.add(new Location(i, j, 0));
                    visited[i][j] = true;
                }
            }
        }

        while (!jihunQueue.isEmpty()) {

            //불이 번진다.
            int fireQueueSize = fireQueue.size();
            for (int i = 0; i < fireQueueSize; i++) {
                Location currentFire = fireQueue.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = currentFire.x + dx[j];
                    int ny = currentFire.y + dy[j];

                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (map[nx][ny] != wall && !visited[nx][ny]) {
                            fireQueue.add(new Location(nx, ny, 0));
                            map[nx][ny] = fire;
                            visited[nx][ny] = true;
                        }
                    }
                }
            }

            // 지훈이가 이동한다.
            int jihunQueueSize = jihunQueue.size();
            for (int i = 0; i < jihunQueueSize; i++) {
                Location currentJihun = jihunQueue.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = currentJihun.x + dx[j];
                    int ny = currentJihun.y + dy[j];

                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (map[nx][ny] == root && !visited[nx][ny]) {
                            jihunQueue.add(new Location(nx, ny, currentJihun.value + 1));
                            map[nx][ny] = jihun;
                            visited[nx][ny] = true;
                        }
                    } else {
                        System.out.println(currentJihun.value + 1);
                        return;
                    }
                }
            }
        }

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

    static class Location {
        int x;
        int y;
        int value;

        public Location(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

}

 

두 개의 큐를 사용해 매 분 동시에 불과 지훈이가 이동하도록 처리하였다. 

 

동시에 불과 지훈이를 핸들링 하기위해 현재 queue의 사이즈 만큼만 딱 반복문을 돌렸고, 이를 통해 매분 한칸씩 불과 지훈이가 이동할 수 있도록 하였다. 

 

그 후 다음 x, y좌표값이 배열 인덱스를 넘어가면 미로를 탈출했다고 보고 출력 후 return하였다.

 

근데 생각해보니 큐를 두개쓰나, 불부터 큐에 넣고 순차적으로 돌리나 어짜피 똑같다고..? 생각을 해서 

 

큐 한개만써서 문제를 다시 풀어보았다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int R;
    static int C;
    static int[][] map;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static final int fire = -1;
    static final int wall = 0;
    static final int jihun = 1;
    static final int root = 2;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];

        for (int i = 0; i < R; i++) {
            s = br.readLine();

            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(j) == '#') {
                    map[i][j] = wall;
                }
                else if (s.charAt(j) == 'J') {
                    map[i][j] = jihun;
                }
                else if (s.charAt(j) == 'F') {
                    map[i][j] = fire;
                }
                else {
                    map[i][j] = root;
                }
            }
        }

        bfs();
    }

    static void bfs() {
        Queue<Location> queue = new LinkedList<Location>();

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == fire) {
                    queue.add(new Location(i, j, 0, fire));
                }
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == jihun) {
                    queue.add(new Location(i, j, 0, jihun));
                }
            }
        }

        while (!queue.isEmpty()) {
            Location temp = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];

                if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                    if (temp.state == fire && map[nx][ny] != wall && map[nx][ny] != fire)  {
                        queue.add(new Location(nx, ny, 0, fire));
                        map[nx][ny] = fire;
                    }
                    if (temp.state == jihun && map[nx][ny] == root) {
                        queue.add(new Location(nx, ny, temp.value + 1, jihun));
                        map[nx][ny] = jihun;
                    }
                }
                if (nx < 0 || nx >= R || ny < 0 || ny >= C) {
                    if (temp.state == jihun) {
                        System.out.println(temp.value + 1);
                        return;
                    }
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

    static class Location {
        int x;
        int y;
        int value;
        int state;

        public Location(int x, int y, int value, int state) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.state = state;
        }
    }

}

 

상식적으로 불과 지훈이가 동시에 같은 칸에 진입할 때는 가지 못하는 것이기 때문에 

 

이를 처리하기 위해서 불을 먼저 큐에 집어넣고 그 다음 지훈이의 처음 위치를 집어넣었다.

 

그러고나서 상태에 맞게 예외처리를 하고 bfs를 돌렸다.

 

풀이 구글링을 해보니 내가 본 풀이는 전부 다 큐 두개를 써서 풀었던데 뭐가 더 좋은 방법인지는 잘모르겠다,,