4179번: 불! - Kotlin, Java (BFS)

4179번: 불!

문제

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

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

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

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

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

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

입력

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

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

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

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

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

출력

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

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

---

 

 

나의 풀이

이 문제는 가장 빠른 탈출 시간, 즉 최단시간을 구해야 하는 문제입니다. 그렇기에 BFS를 사용해서 접근해야 합니다. 다만 이 문제에서는 지훈이만 이동하는 것이 아니라, 불도 함께 이동합니다. 

 

그렇기에 불도 함께 Queue에 넣고 돌립니다. 이를 구분하기 위해 type이란 매개변수를 두었고 이를 이넘 클래스로 보기 좋게 만들어 봤습니다.

 

만약 미로의 모서리에 도착한다면 탈출할 수 있기에 check 함수를 둬서 이를 체크하고 bfs를 종료해줬습니다.

 

 Kotlin

import Point.Type.*
import java.util.LinkedList
import java.util.Queue

val dx = arrayOf(0, 1, -1, 0)
val dy = arrayOf(1, 0, 0, -1)

data class Point(val x: Int , val y : Int, val type: Type) {
    enum class Type { JIHUN, FIRE }
}

lateinit var maze : Array<CharArray>
var jihun = Point(0, 0, JIHUN)
var fire = mutableListOf<Point>()

fun main() = with(System.`in`.bufferedReader()) {

    val (r, c) = readLine().split(" ").map { it.toInt() }

    maze = Array(r) { readLine().toCharArray() }


    for (i in 0 until r) {
        for (j in 0 until c) {
            if (maze[i][j] == 'J')
                jihun = Point(i, j, JIHUN)
            else if (maze[i][j] == 'F')
                fire.add(Point(i, j, FIRE))
        }
    }

    bfs(r, c)
}

fun bfs(r: Int, c: Int) {
    val queue : Queue<Point> = LinkedList()
    val visited = Array(r) { IntArray(c) }

    queue.addAll(fire)

    queue.add(jihun)
    visited[jihun.x][jihun.y] = 1

    while (queue.isNotEmpty()) {
        val (x, y, type) = queue.poll()

        if (type == JIHUN && check(x, y, r, c)) {
            println(visited[x][y])
            return
        }

        for (i in 0 until 4) {
            val tempX = dx[i] + x
            val tempY = dy[i] + y

            if (tempX in 0 until r &&
                tempY in 0 until c &&
                maze[tempX][tempY] == '.') {

                if (type == JIHUN && visited[tempX][tempY] == 0) {
                    visited[tempX][tempY] = visited[x][y] + 1
                    queue.add(Point(tempX, tempY, JIHUN))
                }

                if (type == FIRE) {
                    maze[tempX][tempY] = 'F'
                    queue.add(Point(tempX, tempY, FIRE))
                }
            }
        }
    }

    println("IMPOSSIBLE")
}

fun check(x: Int, y: Int, r: Int, c: Int): Boolean {
    return x == 0 || x == r - 1 || y == 0 || y == c - 1
}

 

 Java

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

public class Main {

    enum Type { JIHUN, FIRE }

    static class Point {
        int x, y;
        Type type;

        Point(int x, int y, Type type) {
            this.x = x;
            this.y = y;
            this.type = type;
        }
    }

    static int[] dx = new int[]{0, 1, -1, 0};
    static int[] dy = new int[]{1, 0, 0, -1};

    static char[][] maze;
    static Point jihun;
    static List<Point> fire = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        maze = new char[r][c];
        for (int i = 0; i < r; i++) {
            String line = bf.readLine();
            for (int j = 0; j < c; j++) {
                maze[i][j] = line.charAt(j);

                if (maze[i][j] == 'J')
                    jihun = new Point(i, j, Type.JIHUN);
                if (maze[i][j] == 'F')
                    fire.add(new Point(i, j, Type.FIRE));
            }
        }

        bfs(r, c);
    }

    static void bfs(int r, int c) {
        int[][] visited = new int[r][c];

        Queue<Point> queue = new LinkedList<>(fire);

        queue.add(jihun);
        visited[jihun.x][jihun.y] = 1;

        while (!queue.isEmpty()) {
            Point temp = queue.poll();
            int x = temp.x;
            int y = temp.y;
            Type type = temp.type;

            if (type == Type.JIHUN && check(x, y, r, c)) {
                System.out.println(visited[x][y]);
                return;
            }

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

                if (tempX >= 0 && tempX < r &&
                        tempY >= 0 && tempY < c &&
                        maze[tempX][tempY] == '.') {

                    if (type == Type.JIHUN && visited[tempX][tempY] == 0) {
                        visited[tempX][tempY] = visited[x][y] + 1;
                        queue.add(new Point(tempX, tempY, Type.JIHUN));
                    }

                    if (type == Type.FIRE) {
                        maze[tempX][tempY] = 'F';
                        queue.add(new Point(tempX, tempY, Type.FIRE));
                    }
                }
            }
        }

        System.out.println("IMPOSSIBLE");
    }
    static boolean check(int x, int y, int r, int c) {
        return x == 0 || x == r - 1 || y == 0 || y == c - 1;
    }
}