프로그래머스 - 미로탈출

최대한 빠르게 미로를 탈출하는데 걸리는 시간을 구해야한다.

즉 최단거리를 구하는 문제라서 나는 bfs 를 선택했다.

 

주의해야할점은 출구를 지나쳐 지나갈 수 있지만 레버를 당기고 와야 출구가 열리기 때문에

레버를 먼저 갔다와야만 탈출을 할 수 있다.

 

여기서 아이디어가 하나 나오는데 bfs를 두번 사용하는것이다.

레버까지 도달하는데 걸리는 최단거리와

레버에서 출구까지 도달하는 최단거리를 각각 구하고 합쳐주는것이다.

 

검색하지 않고 스스로 풀어낸 bfs 풀이라 꽤나 뿌듯하다.

import java.util.*
class Solution {
    var dx = listOf(-1,1,0,0)
    var dy = listOf(0,0,-1,1)  
    var n = 0
    var m = 0
    var checkLaver = false

    
    fun solution(maps: Array<String>): Int {
        var answer: Int = 0
        var laver : Moving? = null
        var start : Moving? = null
        var exit : Moving? = null
        n = maps.size
        m = maps[0].length
        maps.forEachIndexed{ x, map->
            for(y in 0 .. map.length -1){
                if(map[y] == 'L'){
                    laver = Moving(x , y , 0)
                }
                if(map[y] == 'S'){
                    start = Moving(x , y , 0)
                }
                if(map[y] == 'E'){
                    exit = Moving(x , y , 0)
                }
            }
        }
        var startTolever = bfs(maps ,start!! ,laver!!)
        var leverToExit = bfs(maps ,laver!! ,exit!!)
        if(leverToExit == -1 || startTolever == -1){
            answer = -1
        }else{
            answer = startTolever + leverToExit
        }
        return answer
    }
    
    fun bfs(maps : Array<String> , start : Moving ,exit:Moving) : Int{
        var q : Queue<Moving> = LinkedList()
        q.add(start)
        var min = 999999
        val visited = Array(n) { BooleanArray(m) }
        visited[start.x][start.y] = true
        while(q.isNotEmpty()){
            var mv = q.poll()
            if(mv.x == exit.x && mv.y == exit.y){
                return minOf(min , mv.depth)
            }
            
            for(i in 0 .. 3){
                var nx = mv.x + dx[i]
                var ny = mv.y + dy[i]
                if(nx >= 0 && ny>=0 && nx<n && ny < m && !visited[nx][ny] && maps[nx][ny] != 'X'){
                    q.add(Moving(nx,ny,mv.depth + 1))
                    visited[nx][ny] = true
                }
            }
            
        }
        
        return -1
    }
    
    data class Moving(
        var x : Int,
        var y : Int,
        var depth : Int
    )
}