백준 2178번 미로 탐색 - kotlin

오늘은 어제 풀었던 BFS문제 중 미로 탐색이라는 문제이다 시작점에서 도착점까지 최소이동거리를 출력하는 문제.

​

문제

접근 방법

BFS 카테고리에 있는 문제다 보니 당연히 BFS이겠지만, 처음 문제를 읽었을 때는 스택을 이용하는 DFS로 생각하였다.

하지만 DFS는 목표지점까지 도달하는데 방문하는 노드의 수는 적을지라도 항상 옳은 최소거리를 구할 수 없는 방법이였고,

모든 노드를 방문대신 항상 옳은 최소거리를 구할 수 있는 BFS가 옳은 풀이 방식이다.

​

결론

DFS : 목표지점까지 내부적으로는 빠르게 도달할수 있으나 최소거리를 계산하기엔 제한이있음

BFS : 목표지점까지 모든 노드를 순회한 뒤 도달하지만 최소거리를 항상 옳게 도출할수 있음(적절한 풀이 방법)

​

풀이소스

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

//상하좌우 순회를 위한 세팅
val dx = arrayListOf<Int>(0, 1, 0, -1)
val dy = arrayListOf<Int>(1, 0, -1, 0)


fun bfs(N: Int, M: Int, map: Array<Array<Int>>) {
    val queue = mutableListOf<Pair<Int, Int>>() //큐를 기록할 리스트
    val visited = Array(N) { Array(M, { 0 }) }  //방문 체크를 위한 어레이
    val distance = Array(N) { Array(M, { 0 }) }  //거리를 기록할 어레이

    visited[0][0] = 1 //처음 좌표 방문표시
    distance[0][0] = 1 //처음 거리 1 세팅
    queue.add(Pair(0, 0)) //큐에 좌표추가

    //큐에 값이 없을때까지 반복
    while (!queue.isEmpty()) {
        var temp = queue.removeAt(0)  //큐의 값을 활용하기 위해 삭제하면서 템프 변수에 저장

        // 상하좌우 순회
        for (i in 0 until 4) {
            var move_x = temp.first + dx[i]
            var move_y = temp.second + dy[i]
            //맵을 벗어나지않으며, 갈수있는 좌표이면서 방문하지 않은 좌표이면
            if (move_x >= 0 && move_x < N && move_y >= 0 && move_y < M && map[move_x][move_y] == 1 && visited[move_x][move_y] == 0) {
                queue.add(Pair(move_x, move_y)) //큐에 좌표 추가
                visited[move_x][move_y] = 1  //방문표시
                distance[move_x][move_y] = distance[temp.first][temp.second] + 1  //거리 = 전 좌표의 값 + 1
            }
        }
    }
    print("${distance[N - 1][M - 1]}")
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (N, M) = readLine().split(" ").map { it.toInt() }
    val map = Array(N) { Array(M, { 0 }) }

    //맵 셋팅
    for (i in 0 until N) {
        val st = readLine().split("").run { subList(1, this.lastIndex) }
        for (j in 0 until M) {
            map[i][j] = st[j].toInt()
        }
    }
    bfs(N, M, map)
}

유용한 정보

1. 상하좌우 순회용 x, y 좌표 리스트를 선언하여 포문으로 돌리는 방식, 매우 간편했다.

2. readLine()을 한글자씩 분리하면 맨 앞과 뒤에 빈 공백의 요소가 생긴다. 그래서 subList를 통해 앞뒤를 뺀 인덱스만 리스트로 재구성하였다.

​

​

마침

이번 BFS에선 큐를 사용하지 않고 List를 이용하여 큐 처럼 사용하였다

적절한 자료구조를 사용하는게 좋겠지만 사용 방법을 모를땐 본인만의 방식으로 문제를 풀어낼수만 있다면 좋은거겠지..?