[프로그래머스][Koltin] 미로 탈출

해당문제는 BFS를 알고 있다면 풀 수 있는 문제 였습니다.

일반적인 BFS문제와 다른 점이 있다면 BFS를 두 번 돌려서 문제를 풀 수 있다는 점입니다.

물론 절대적은 아닙니다. 사람에 따라 한 번 돌려서 작성 할 수 있지만 저의 경우 아직 공부하고 있는 중이라

두번 돌려야 해당 문제를 통과 할 수 있었습니다.

 

저도 처음에는 레버(L) 이 나오면 visited 를 레버 위치만 제외하고 true로 바꾼다음 계산하는 방식을 하였으나,

실력 부족으로 해당 로직으로 작성하면 시간초과가 나왔었습니다.

추후 실력이 더욱 상승하면 bfs를 한 번만 돌려 통과할 수 있는 코드를 작성해 보겠습니다.

 

하기는 작성한 코드와 실행결과 입니다.

 

class Solution {
    fun solution(maps: Array<String>): Int {
        var answer: Int
        val arrX = intArrayOf(1,-1,0,0)
        val arrY = intArrayOf(0,0,1,-1)

        var mapCount = ArrayList<IntArray>()
        var visit = ArrayList<BooleanArray>()
        var dq = java.util.ArrayDeque<Node>()
        var start = Node(0,0)
        var end = Node(0,0)
        var leval = Node(0,0)
        for(i in 0 .. maps.size-1){
            mapCount.add(IntArray(maps[i].length){0})
            visit.add(BooleanArray(maps[i].length){true})
            for(j in 0 .. maps[i].length-1){
                if(maps[i][j] == 'S') start = Node(i,j)
                if(maps[i][j] == 'E') end = Node(i,j)
                if(maps[i][j] == 'L') leval = Node(i,j)
            }
        }

        dq.add(start)
        var startleval = -1
        while (!dq.isEmpty()) {
            val now = dq.pollFirst()
            val nowX = now.x
            val nowY = now.y
            visit[nowX][nowY] = false
            if (now.equals(leval) ) {
                startleval = mapCount[nowX][nowY]
                break
            }

            for(i in 0 .. 3){
                val rx = arrX[i]
                val ry = arrY[i]
                val nowValue = mapCount[nowX][nowY]

                if(nowX+rx < 0 || nowY+ry < 0 || nowX+rx >= maps.size || nowY+ry >= maps[0].length) continue

                if(!visit[nowX+rx][nowY+ry] || maps[nowX+rx][nowY+ry].equals('X')) continue

                if(mapCount[nowX+rx][nowY+ry] == 0) {
                    mapCount[nowX + rx][nowY + ry] = nowValue + 1

                    dq.addLast(Node(nowX + rx, nowY + ry))
                }
            }
        }


        dq.clear()

        dq.addFirst(leval)
        for(i in 0 .. visit.size-1){
            for(j in 0 .. visit[i].size-1){
                visit[i][j] = true
                mapCount[i][j] = 0
            }
        }

        var levalend = -1
        while (!dq.isEmpty()){
            val now = dq.pollFirst()
            val nowX = now.x
            val nowY = now.y
            visit[nowX][nowY] = false

            if (now.equals(end)) {
                levalend = mapCount[nowX][nowY]
                break
            }

            for(i in 0 .. 3){
                val rx = arrX[i]
                val ry = arrY[i]
                val nowValue = mapCount[nowX][nowY]

                if(nowX+rx < 0 || nowY+ry < 0 || nowX+rx >= maps.size || nowY+ry >= maps[0].length) continue

                if(!visit[nowX+rx][nowY+ry] || maps[nowX+rx][nowY+ry].equals('X')) continue

                if(mapCount[nowX+rx][nowY+ry] == 0) {
                    mapCount[nowX + rx][nowY + ry] = nowValue + 1

                    dq.addLast(Node(nowX + rx, nowY + ry))
                }
            }

        }

        answer = startleval + levalend
        if(startleval.equals(-1) || levalend.equals(-1)) {
            answer = -1
        }
        return answer
    }
}
data class Node(
    val x: Int,
    val y: Int
)

테스트 1 〉	통과 (0.71ms, 59.6MB)
테스트 2 〉	통과 (0.83ms, 61.4MB)
테스트 3 〉	통과 (0.84ms, 60.5MB)
테스트 4 〉	통과 (0.56ms, 60MB)
테스트 5 〉	통과 (0.69ms, 59.5MB)
테스트 6 〉	통과 (0.73ms, 60.8MB)
테스트 7 〉	통과 (3.25ms, 59.6MB)
테스트 8 〉	통과 (6.60ms, 59.6MB)
테스트 9 〉	통과 (0.66ms, 58.7MB)
테스트 10 〉	통과 (0.62ms, 58.5MB)
테스트 11 〉	통과 (1.76ms, 60.1MB)
테스트 12 〉	통과 (7.92ms, 59.6MB)
테스트 13 〉	통과 (12.14ms, 59.4MB)
테스트 14 〉	통과 (3.93ms, 59.6MB)
테스트 15 〉	통과 (1.23ms, 62.4MB)
테스트 16 〉	통과 (13.22ms, 60.3MB)
테스트 17 〉	통과 (11.89ms, 62.8MB)
테스트 18 〉	통과 (0.88ms, 60.9MB)
테스트 19 〉	통과 (0.76ms, 61.2MB)
테스트 20 〉	통과 (8.49ms, 61MB)
테스트 21 〉	통과 (2.16ms, 60.9MB)
테스트 22 〉	통과 (1.05ms, 59.2MB)
테스트 23 〉	통과 (0.43ms, 61.2MB)