2178번: 미로 탐색 - Kotlin (BFS)

2178번: 미로 탐색

 

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

나의 풀이

이 문제는 그래프 탐색 문제이며, 우리는 그래프 탐색을 할때 DFS와 BFS 방식을 사용한다.

DFS는 모든 경로를 확인하여 그 중에서 가장 짧은 경로를 선택한다. 

BFS는 처음 마지막 좌표에 도착한 시점의 경로가 가장 짧은 경로이다.  그럼으로 이와 같은 최단경로 문제일때는 BFS를 사용하여야 한다.

 

 처음 내가 설계를 하려고 했을때는 무작정 모든 경로를 직접 대입하여로 하였다. 하지만 dx, dy와 같이 위, 아래, 좌, 우를 쉽게 나타낼 수 있는 방법이 있었고, 이 4가지 경우의 수를 가지고 문제를 해결하였다.

 

import java.util.LinkedList
import java.util.Queue

var visited = Array(0) { Array(0) { false } }
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }

    visited = Array(n) { Array(m) { false } }

    val maze = Array(n) { readLine().map { it.toString().toInt() }.toIntArray() }

    bfs(0, 0, n, m, maze)
}


fun bfs(x: Int, y: Int, n: Int, m: Int, maze: Array<IntArray>) {
    val queue: Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()
    queue.add(x to y)
    visited[x][y] = true

    while (queue.isNotEmpty()){
        val now = queue.poll()
        for(i in 0 until 4){
            val tempX = now.first + dx[i]
            val tempY = now.second + dy[i]

            if(tempX in 0 until n
                && tempY in 0 until m
                && !visited[tempX][tempY]
                && maze[tempX][tempY] != 0 ){
                visited[tempX][tempY] = true
                maze[tempX][tempY] = maze[now.first][now.second] + 1
                queue.add(tempX to tempY)
            }
        }
    }
    println(maze[n - 1][m - 1])
}

 

다만 처음 문제를 풀때 queue의 넣는 형식을 Pair의 형식이 아니라 그냥 list의 형식으로 넣어주었는데 제대로 작동하지 않았었다. 이유를 찾아보고 더 발전하는 계기가 될 것이다.