프로그래머스 - 미로 탈출(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/159993?language=kotlin

 

[문제 설명]

레버 당기고 나가세요.

 

[접근 방법]

최단거리 두 번 구하기

 

import java.util.LinkedList

fun main() {
    val solutionObject = Solution()
    println(solutionObject.solution(arrayOf("SOOOL","XXXXO","OOOOO","OXXXX","OOOOE")).equals(16))
    println(solutionObject.solution(arrayOf("LOOXS","OOOOX","OOOOO","OOOOO","EOOOO")).equals(-1))
}

class Solution {
    private lateinit var startPoint: Pair<Int, Int>
    private lateinit var leverPoint: Pair<Int, Int>
    private lateinit var exitPoint: Pair<Int, Int>
    fun solution(maps: Array<String>): Int {
        // 벽은 지날 수 없다.
        // 레버를 당겨서 문을 연다.
        // 1. 레버로 향한다.
        // 2. 문으로 간다.

        // 구해야하는 것.
        // 1. S -> L
        // 2. L -> E

        // 생각나는 방법 1. BFS를 통해 시작점(S)부터 레버(L)까지 최단 거리 구하기 + 레버(L)부터 출구(E)까지 거리
        // 보완 방법 : 시작점에서 레버로 가는 길에 출구가 있을 경우. (시작점 -> 레버) - (시작점 -> 출구) = (레버 -> 출구)
        // 시간복잡도 : O(V + E) + O(V + E) = O(V + E)
        // 생각나는 방법 2. 플로이드 와샬 알고리즘을 통해 구하기. 모든 정점간에 거리.
        // 시간복잡도 O(V^3)
        maps.forEachIndexed { idxOfRow, row ->
            row.toCharArray().forEachIndexed { idxOfCol, node ->
                if (node.equals('S')) {
                    startPoint = idxOfRow to idxOfCol
                } else if (node.equals('E')) {
                    exitPoint = idxOfRow to idxOfCol
                } else if (node.equals('L')) {
                    leverPoint = idxOfRow to idxOfCol
                }
            }
        }

        val distanceStartToLever = getMinDistance(startPoint, leverPoint, maps)
        if (distanceStartToLever == Int.MAX_VALUE) {
            return -1
        }
        val distanceLeverToExit = getMinDistance(leverPoint, exitPoint, maps)
        if (distanceLeverToExit == Int.MAX_VALUE) {
            return -1
        }
        return distanceLeverToExit + distanceStartToLever
    }

    private fun getMinDistance(startPoint: Pair<Int, Int>, endPoint: Pair<Int, Int>, maps: Array<String>): Int {
        val directions = arrayOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)
        var distance = -1
        val visited = Array(maps.size) { BooleanArray(maps[0].length) { false } }
        val queue = LinkedList<Pair<Int, Int>>()
        queue.offer(startPoint)
        visited[startPoint.first][startPoint.second] = true

        while (queue.isNotEmpty()) {
            distance++
            repeat(queue.size) {
                val node = queue.poll()
                if (node.first == endPoint.first && node.second == endPoint.second) {
                    return distance
                }

                directions.forEach {
                    val nextPoint = node.first + it.first to node.second + it.second
                    if (nextPoint.first in maps.indices && nextPoint.second in maps[0].indices && !visited[nextPoint.first][nextPoint.second] && maps.get(nextPoint.first)[nextPoint.second] != 'X') {
                        queue.offer(nextPoint)
                        visited[nextPoint.first][nextPoint.second] = true
                    }
                }
            }
        }

        return Int.MAX_VALUE
    }
}