백준 [4179] kotlin

[문제]

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

4179번: 불!

[풀이]

불을 피해서 벽이 아닌 가장자리로 가는데, 가장 짧은 시간을 구하는 문제이다.

불은 상하좌우로 번지며, 탈출을 위한 이동도 상하좌우로만 이동할 수 있다.

 

너비 우선 탐색을 이용하여 풀었다.

 

입력받은 미로를 arr이라고 가정한다.

 

bfs를 시간별로 반복하면서, 

인자로 현재 위치와, 다음 번질 불의 위치를 넣는다.

그리고 다음 번질 불의 위치를 arr에 불로 최신화를 해준다. 그리고 불의 위치 상하좌우 방향을 다음 번질 불의 위치를 배열에 저장한다.

현재 위치를 기준으로 상하좌우로 방문하지 않은 위치중 탈출이 가능하면 true를 반환하고, 방문을 하지 않고 이동가능한 위치라면 다음 이동할 곳이 담긴 배열에 저장을 한다.

 

만약 다음 이동할 곳이 담긴 배열의 크기가 0이라면, 다음으로 이동할 곳이 없다라는 뜻이므로 IMPOSSIBLE한 경우이다.

만약 0보다 크면 다시 bfs 배열을 호출하고 인자로 방문할 위치와, 다음 번질 불의 위치를 인자로 넣어준다.

 

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter



lateinit var arr : ArrayList<CharArray>
lateinit var fireList : ArrayList<Pair<Int, Int>>
lateinit var visit : ArrayList<BooleanArray>
var R = 0
var C = 0
var ans = 1
lateinit var start : ArrayList<Pair<Int,Int>>
var dx = listOf(0,0,1,-1)
var dy = listOf(1,-1,0,0)
fun main() {
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))

    val tmp = br.readLine().split(" ").map { it.toInt() }
    R = tmp[0]
    C = tmp[1]
    arr = arrayListOf()
    visit = arrayListOf()
    fireList = arrayListOf()
    repeat(R)
    {
        visit.add(BooleanArray(C){false})
        arr.add(br.readLine().toCharArray())
    }
    start = arrayListOf()
    for(i in 0 until R)
    {
        for(j in 0 until C)
        {
            if(arr[i][j] == 'F') fireList.add(Pair(i,j))
            else if(arr[i][j] == 'J') {
                start.add(Pair(i,j))
                visit[i][j] = true
            }
        }
    }
    val x = start[0].first
    val y = start[0].second
    if(((x == 0 || x == R-1) && y in 0 until C) || (x in 0 until R &&(y == 0 || y == C-1))) bw.write("1")
    else{
        if(bfs(start, fireList)) bw.write(ans.toString())
        else bw.write("IMPOSSIBLE")
    }
    bw.flush()
    bw.close()
}

fun bfs(start : ArrayList<Pair<Int, Int>>, fireList: ArrayList<Pair<Int,Int>>) : Boolean
{
    var nextMove = arrayListOf<Pair<Int,Int>>()
    var nextFire = arrayListOf<Pair<Int,Int>>()
    ans++
    fireList.forEach()
    {
        it ->
        repeat(4)
        {
            i ->
            val nx = it.first + dx[i]
            val ny = it.second + dy[i]
            if(nx in 0 until R && ny in 0 until C && arr[nx][ny] != '#' && arr[nx][ny] != 'F')
            {
                arr[nx][ny] = 'F'
                nextFire.add(Pair(nx,ny))
            }
        }
    }
    start.forEach()
    {
        it ->
        repeat(4)
        {
            i ->
            val nx = it.first + dx[i]
            val ny = it.second + dy[i]
            if(((nx == 0 || nx == R-1) && ny in 0 until C) || (nx in 0 until R &&(ny == 0 || ny == C-1))){
                if(arr[nx][ny] == '.') return true
            }
            if(nx in 0 until R && ny in 0 until C && arr[nx][ny] == '.' && !visit[nx][ny])
            {
                visit[nx][ny] = true
                nextMove.add(Pair(nx,ny))
            }
        }
    }
    if(nextMove.size == 0) return false
    return bfs(nextMove, nextFire)
}