[백준/Kotlin] 불(5427)

문제

https://www.acmicpc.net/problem/5427

 

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

 

[ 입력 ]

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

 

[ 출력 ]

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

 

---

풀이

- 불과 상근이의 이동을 체크

// 백준 - 불(5427)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
import java.util.LinkedList
import java.util.Queue

data class Fire (
  val x: Int,
  val y: Int
)
data class Person (
  val x: Int,
  val y: Int,
  val time: Int
)

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

var map: Array<Array<Char>> = arrayOf()            // 빌딩 지도
var person = LinkedList<Person>() as Queue<Person> // 상근이 위치
var fire = LinkedList<Fire>() as Queue<Fire>       // 불 위치

var w = 0
var h = 0
var testResult = 0

fun main() {
  val br = BufferedReader(InputStreamReader(System.`in`))

  val T = br.readLine().toInt()
  var answer = StringBuilder()

  for(i: Int in 0..T-1) {
    val st = StringTokenizer(br.readLine())
    w = st.nextToken().toInt() // 너비
    h = st.nextToken().toInt() // 높이

    map = Array(h, {Array(w,{' '})})               // 빌딩 지도
    person = LinkedList<Person>() as Queue<Person> // 상근이 위치
    fire = LinkedList<Fire>() as Queue<Fire>       // 불 위치

    for(j: Int in 0..h-1) {
      val input = br.readLine()
      for(k: Int in 0..w-1) {
        map[j][k] = input[k]
        if(map[j][k].equals('@')) person.offer(Person(j, k, 0))
        else if(map[j][k].equals('*')) fire.offer(Fire(j, k))
      }
    }

    testResult = 0
    bfs()
    if(testResult == 0)
      answer.append("IMPOSSIBLE\n")
    else
      answer.append(testResult).append("\n")
  }

  print(answer)
}

fun bfs() {
  while(!person.isEmpty()) {
    val fireCnt = fire.size
    val personCnt = person.size

    for(i: Int in 0..fireCnt-1) {
      val cur = fire.poll()
      // 불이 상하좌우로 번짐
      for(j: Int in 0..3) {
        val moveX = cur.x + dx[j]
        val moveY = cur.y + dy[j]

        // 공간 범위 벗어나거나 이미 불인 경우, 벽인 경우 패스
        if(moveX < 0 || moveX >= h || moveY < 0 || moveY >= w || map[moveX][moveY].equals('#') || map[moveX][moveY].equals('*')) continue

        // 불 번짐
        map[moveX][moveY] = '*'
        fire.offer(Fire(moveX, moveY))
      }
    }

    for(i: Int in 0..personCnt-1) {
      val cur = person.poll()
      // 상근이가 상하좌우로 이동
      for(j: Int in 0..3) {
        val moveX = cur.x + dx[j]
        val moveY = cur.y + dy[j]

        // 공간 범위 벗어나면 탈출 성공
        if(moveX < 0 || moveX >= h || moveY < 0 || moveY >= w) {
          testResult = cur.time + 1
          return
        }

        // 이동 가능한 길이면 이동
        if(map[moveX][moveY].equals('.')) {
          map[moveX][moveY] = '@' // 재방문 방지
          person.offer(Person(moveX, moveY, cur.time + 1))
        }
      }
    }
  }
}