[백준][코틀린] 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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

예제 입력	예제 출력
4 6 101111 101010 101011 111011	15
4 6 110110 110110 111111 111101	9
2 25 1011101110111011101110111 1110111011101110111011101	38
7 7 1011111 1110001 1000001 1000001 1000001 1000001 1111111	13

 

문제 풀이

DFS는 최단거리를 찾으려면 완전 탐색을 하고 그중 가장 작은 값을 선택해야 하는데 경로가 매우 많을 수 있기때문에 시간 복잡도가 매우 커진다. 반면 BFS는 최단거리를 보장하기 때문에 최단 거리 구하기 문제 또한 BFS의 전형적인 예시라 할 수 있다. 

BFS의 원리를 그대로 적용한 코드이기에 크게 설명은 덧붙히지 않는다.

</>̆̈ 코드

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

private val br = BufferedReader(InputStreamReader(System.`in`))
private val nm = br.readLine().split(" ").map { it.toInt() }
private val maze = Array(nm[0]) { br.readLine().map { it.toString().toInt() }.toIntArray() }
private val visited = Array(nm[0]) {BooleanArray(nm[1])}
private val steps = listOf(Pair(0, 1), Pair(1, 0), Pair(0, -1),Pair(-1, 0))


fun main() {
    bfs(0 to 0)
    print(maze[nm[0]-1][nm[1]-1])
}

private fun bfs(point: Pair<Int, Int>) {
    visited[point.first][point.second] = true
    val list = LinkedList<Pair<Int, Int>> ()
    list.add(point)

    while (list.isNotEmpty()) {
        val curPoint = list.poll()
        for (step in steps) {
            val newPoint = curPoint.first + step.first to curPoint.second + step.second
            if (newPoint.first in 0 until nm[0]
                && newPoint.second in 0 until nm[1]
                && !visited[newPoint.first][newPoint.second]
                && maze[newPoint.first][newPoint.second] != 0) {
                list.add(newPoint)
                maze[newPoint.first][newPoint.second] = maze[curPoint.first][curPoint.second] + 1
                visited[newPoint.first][newPoint.second] = true
            }
        }
    }
}

링크

2178번: 미로 탐색