백준 - 13459 구슬 탈출 (코틀린)

[문제]

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

13459번: 구슬 탈출

[풀이]

bfs를 이용하여 푼다. 두 구슬이 같이 움직이니 큐에는 구슬 각각의 좌표를 같이 넣어주고, 움직인 횟수도 같이 넣어준다. 움직인 횟수가 10번이상이면 0을 반환한다. 큐에서 나온 각각의 좌표를 방향마다 벽이나 구멍을 만날때 까지 움직인 좌표를 구하고 각각의 좌표가 이미 방문했는지 안했는지 체크하고 방문하지 않았으면 큐에 넣어준다. 이 때 좌표를 움직일 때 두 개의 좌표가 같다면 같은 선상에 있다는 뜻이고 움직이기전의 좌표와의 차이를 통해 더 많이 움직인 좌표의 구슬이 다른 구슬보다 뒤에 있다는 뜻이므로 움직인 이후의 좌표에서 해당 방향 반대로 한칸 움직여준다. 위 작업을 반복하면서 만약 파란 구슬이 빠지지 않은 상태에서 빨간 구슬이 구멍에 도달했다면 1을 반환하고 큐가 빌 때 까지 1을 반환하지 않는다면 0을 출력한다.

[코드]

import java.util.*

private var n = 0
private var m = 0
private lateinit var arr : Array<CharArray>
private lateinit var visited : Array<Array<Array<BooleanArray>>>
private val dx = listOf(-1,0,1,0)
private val dy = listOf(0,1,0,-1)
private lateinit var red : Pair<Int,Int>
private lateinit var blue : Pair<Int,Int>
private lateinit var queue : Queue<Triple<Pair<Int,Int>,Pair<Int,Int>,Int>>

fun main() {
    val br = System.`in`.bufferedReader()
    br.readLine().split(" ").map { it.toInt() }.apply {
        n = this[0]
        m = this[1]
    }
    arr = Array(n) { CharArray(m) }
    visited = Array(n) { Array(m){ Array(n){BooleanArray(m)} } }
    queue = ArrayDeque()
    repeat(n){
        arr[it] = br.readLine().toCharArray()
        arr[it].forEachIndexed { idx,s ->
            if(s == 'R')
                red = Pair(it,idx)
            if(s == 'B')
                blue = Pair(it,idx)
        }
    }
    queue.add(Triple(red,blue,0))
    visited[red.first][red.second][blue.first][blue.second] = true
    bfs()

}
private fun bfs(){
    while(queue.isNotEmpty()){
        val q = queue.poll()
        val (redX,redY) = q.first
        val (blueX,blueY) = q.second
        val cnt = q.third
        if(cnt >= 10) break
        for(i in 0 .. 3){
            var (nnRedX,nnRedY,redCnt)=move(Pair(redX,redY),i)
            var (nnBlueX,nnBlueY,blueCnt)=move(Pair(blueX,blueY),i)
            if(arr[nnRedX][nnRedY]=='O' && arr[nnBlueX][nnBlueY]!='O'){
                println(1)
                return
            }
            if(arr[nnBlueX][nnBlueY]=='O') {
                continue
            }
            if(nnRedX == nnBlueX && nnRedY == nnBlueY){
                if(redCnt>blueCnt){
                    nnRedX -= dx[i]
                    nnRedY -= dy[i]
                }
                else {
                    nnBlueX -= dx[i]
                    nnBlueY -= dy[i]
                }
            }
            if(visited[nnRedX][nnRedY][nnBlueX][nnBlueY]) continue
            visited[nnRedX][nnRedY][nnBlueX][nnBlueY] = true
            queue.add(Triple(Pair(nnRedX,nnRedY), Pair(nnBlueX,nnBlueY),cnt+1))
        }
    }
    println(0)
}
private fun move(point:Pair<Int,Int>,dir:Int):Triple<Int,Int,Int>{
    var (x, y) = point
    var cnt = 0
    while(arr[x+dx[dir]][y+dy[dir]] != '#' && arr[x][y]!= 'O'){
        x += dx[dir]
        y += dy[dir]
        cnt += 1
    }
    return Triple(x,y,cnt)
}