<프로그래머스> 미로 탈출(Lv.2)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/%EB%AF%B8%EB%A1%9C%20%ED%83%88%EC%B6%9C

[프로그래머스]

https://school.programmers.co.kr/learn/courses/30/lessons/159993

제출 결과

 

생각보다 쉽게 풀어낸 문제였다.

오랜만에 프로그래머스 문제를 푸는데 이 문제는 보자마자 BFS에 경로를 두 번 나눠야겠다는 생각이 빡! 들었다.

그래서 바로 코드로 생각을 풀어내기 시작했다.

 

가장 먼저 두 개의 큐에 시작 지점 좌표와 레버 좌표를 넣었다.

두 개의 큐인 이유는 시작 지점에서 레버, 레버에서 출구로 가는 BFS를 따로 돌릴 것이기 때문이다.

레버를 당기지 못하면 출구로 빠르게 가도 나갈 수 없으니 그렇게 나눴다.

 

그리고 일반적인 BFS로 진행했다.

첫번째 BFS에서는 레버에 도착하면 현재까지 걸린 시간을 리턴하고 도착하지 못하면 0을 리턴한다.

그래서 answer의 값에 변화가 없는 경우 결과로 -1을 리턴하고 변화가 있다면 다음 BFS를 진행한다.

두번째 BFS에서는 출구에 도착하면 현재까지 걸린 시간을 리턴하고 도착하지 못하면 0을 리턴한다.

그래서 temp 변수로 받은 값이 0이면 결과로 -1을 리턴하고 아니라면 answer에 temp를 더한 값을 결과로 리턴한다.

 

제출했을 때 하나의 테스트 케이스만 틀렸었는데 그건 레버까지는 도착을 했지만 레버에서 출구로 가는 경로가 없는 경우였다.

그래서 이에 대한 조건 처리를 해주니 통과했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

class Solution {
    private var startQ = ArrayDeque<Pair<Int,Int>>()
    private var leverQ = ArrayDeque<Pair<Int,Int>>()

    private lateinit var visitedStartQ: Array<Array<Boolean>>
    private lateinit var visitedLeverQ: Array<Array<Boolean>>

    lateinit var exitPos: Pair<Int, Int>

    private val dy = listOf(0, 1, 0, -1)
    private val dx = listOf(1, 0, -1, 0)

    fun solution(maps: Array<String>): Int {
        var answer: Int = 0

        visitedStartQ = Array(maps.size) { Array(maps[0].length) { false } }
        visitedLeverQ = Array(maps.size) { Array(maps[0].length) { false } }

        maps.forEachIndexed { idxRow, row ->
            row.forEachIndexed { idxCol, col ->
                when (col) {
                    'S' -> {
                        startQ.add(Pair(idxRow, idxCol))
                        visitedStartQ[idxRow][idxCol] = true
                    }
                    'L' -> {
                        leverQ.add(Pair(idxRow, idxCol))
                        visitedLeverQ[idxRow][idxCol] = true
                    }
                    'E' -> exitPos = Pair(idxRow, idxCol)
                }
            }
        }

        answer += startToLever(maps)
        if (answer == 0) return -1

        val temp = leverToExit(maps)
        return if (temp == 0) -1 else answer + temp
    }

    private fun startToLever(maps: Array<String>): Int {
        var count = 0

        startQ.add(Pair(-1, -1))
        while (startQ.isNotEmpty()) {
            val cur = startQ.removeFirst()

            if (cur.first == -1) {
                if (startQ.isNotEmpty()) {
                    count++
                    startQ.add(Pair(-1, -1))
                }
                continue
            }

            if (maps[cur.first][cur.second] == 'L') return count

            for (i in 0..3) {
                val newRow = cur.first + dy[i]
                val newCol = cur.second + dx[i]

                if (newRow < 0 || newRow >= maps.size || newCol < 0 || newCol >= maps[0].length) continue
                if (visitedStartQ[newRow][newCol]) continue
                if (maps[newRow][newCol] == 'X') continue

                startQ.add(Pair(newRow, newCol))
                visitedStartQ[newRow][newCol] = true
            }
        }

        return 0
    }

    private fun leverToExit(maps: Array<String>): Int {
        var count = 0

        leverQ.add(Pair(-1, -1))
        while (leverQ.isNotEmpty()) {
            val cur = leverQ.removeFirst()

            if (cur.first == -1) {
                if (leverQ.isNotEmpty()) {
                    count++
                    leverQ.add(Pair(-1, -1))
                }
                continue
            }

            if (maps[cur.first][cur.second] == 'E') return count

            for (i in 0..3) {
                val newRow = cur.first + dy[i]
                val newCol = cur.second + dx[i]

                if (newRow < 0 || newRow >= maps.size || newCol < 0 || newCol >= maps[0].length) continue
                if (visitedLeverQ[newRow][newCol]) continue
                if (maps[newRow][newCol] == 'X') continue

                leverQ.add(Pair(newRow, newCol))
                visitedLeverQ[newRow][newCol] = true
            }
        }

        return 0
    }
}