백준 - 미로 탐색(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2178

 

[문제 설명]

도착점까지 걸리는 거리를 구하시오.

 

[접근 방법]

최단 거리이므로 BFS를 이용한 그래프 순회로 풀었다.

정점의 개수는 총 N*M 간선의 개수는 N*M*4

=> 시간복잡도는 최악의 경우 모든 정점과 간선을 확인하는 Bfs이므로

V: 정점의 개수 E: 간선의 개수 O(V+E) -> O(N*M+4*N*M) -> O(NM)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var map: Array<IntArray>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var (lenOfRow, lenOfColumn) = readLine().split(" ").map { it.toInt() }
    map = Array(lenOfRow){IntArray(lenOfColumn)}
    repeat(lenOfRow) {
        readLine().forEachIndexed { index, c ->
            map[it][index] = c.digitToInt()
        }
    }

    if (lenOfRow == 1 && lenOfColumn == 1) {
        if (map[0][0] == 1) {
            println(1)
        } else {
            println(-1)
        }
        return
    }

    println(bfs(intArrayOf(0,0), lenOfRow, lenOfColumn))
}

fun bfs(position: IntArray, lenOfRow: Int, lenOfColumn: Int): Int {
    var distance = 1
    val isVisited = Array(map.size) {BooleanArray(map[0].size)}
    isVisited[0][0] = true
    val directions = arrayOf(intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1))
    val q = LinkedList<IntArray>()
    q.offer(position)

    while (!q.isEmpty()) {
        val size = q.size
        for (i in 1..size) {
            val currentPosition = q.poll()
            for (direction in directions) {
                val nextPosition = intArrayOf(currentPosition[0]+direction[0], currentPosition[1]+direction[1])

                if (nextPosition[0] == lenOfRow-1 && nextPosition[1] == lenOfColumn-1) {
                    return distance+1
                }
                if (nextPosition[0] in 0 until lenOfRow && nextPosition[1] in 0 until lenOfColumn) {
                    if (map[nextPosition[0]][nextPosition[1]] == 0) {
                        continue
                    }

                    if (!isVisited[nextPosition[0]][nextPosition[1]]) {
                        q.offer(nextPosition)
                        isVisited[nextPosition[0]][nextPosition[1]] = true
                    }
                }
            }
        }
        distance++
    }

    return -1
}

 

[반성할 점]

이번 문제도 시간을 측청하고 풀었는데 정확히 30분이 걸렸다. 좀 더 빨리 풀 수 있을 거라고 생각했는데 아직 코틀린이 익숙하지 않은가보다.

특히 2차원 배열 만들 때, 아직도 가끔 헷갈린다.

또한, until과 .. 분명 구분을 했는데 막상 코드로 쓰면 순간적으로 캐치가 되지 않는다.

until은 -1까지 ..은 그 수를 포함인데 자꾸 까먹는다...

다시 한 번 명확히 하자.

 

kotlin으로 그래프 문제를 풀 때마다 느끼는 점이지만, 이 in 키워드가 진짜 좋은듯하다.

자바의 경우 0 <= a && a <= lenOfColumn-1 이런 식으로 해야 하는데, in을 사용하면 이를 쉽게 간략화할 수 있다.

그래프 문제마다 유용하게 써야겠다.