[백준] 2178. 미로 탐색 (Kotlin)

문제 : www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

DFS

import kotlin.math.min

lateinit var map : Array<Array<Int>>
lateinit var visit : Array<Array<Int>>
var n = 0
var m = 0
var min = 1000000

fun main() = with(System.`in`.bufferedReader()){
    val tmp = readLine().split(" ").map { it.toInt() }
    n = tmp[0]
    m = tmp[1]

    map = Array(n+2){Array(m+2){0} }
    visit = Array(n+2){Array(m+2){0} }

    for(i in 1 .. n){
        val line = readLine().toString()
        for(j in 0 until m){
            map[i][j+1] = line[j]-'0'
        }
    }

    find(1,1,0)
    println(min+1)
}

fun find(x : Int, y : Int, sum : Int){

    if(x==n && y==m) {
        min = min(min,sum)
        return
    }

    // 상
    if(map[x-1][y] == 1 && visit[x-1][y] == 0){
        visit[x-1][y] = 1
        find(x-1,y,sum+1)
        visit[x-1][y] = 0
    }
    // 하
    if(map[x+1][y] == 1 && visit[x+1][y] == 0){
        visit[x+1][y] = 1
        find(x+1,y,sum+1)
        visit[x+1][y] = 0
    }
    // 좌
    if(map[x][y-1] == 1 && visit[x][y-1] == 0){
        visit[x][y-1] = 1
        find(x,y-1,sum+1)
        visit[x][y-1] = 0
    }
    // 우
    if(map[x][y+1] == 1 && visit[x][y+1] == 0){
        visit[x][y+1] = 1
        find(x,y+1,sum+1)
        visit[x][y+1] = 0
    }
}

처음에는 DFS 방식으로 풀었다가

계속 시간초과가 발생하여 BFS 방식으로 변경하였다.

 

BFS

import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    val tmp = readLine().split(" ").map { it.toInt() }
    var que = LinkedList<Pair<Int,Int>>()
    var n = tmp[0]
    var m = tmp[1]
    var count = 0

    // 상하좌우
    val dx = listOf(-1,1,0,0)
    val dy = listOf(0,0,-1,1)

    // 가장자리 띄어줌
    val map = Array(n+2){Array(m+2){0} }
    val visit = Array(n+2){Array(m+2){0} }

    for(i in 1 .. n){
        val line = readLine().toString()
        for(j in 0 until m){
            map[i][j+1] = line[j]-'0'
        }
    }

    que.add(Pair(1,1))

    while (que.isNotEmpty()){
        count++ // 레벨 카운트
        for(q in 0 until que.size) {
            val pop = que.poll()
            val x = pop.first
            val y = pop.second

            // 목표 도달시 리턴
            if (x == n && y == m) return println(count)

            for (i in 0 until 4) {
                val nx = x + dx[i]
                val ny = y + dy[i]
                if (map[nx][ny] == 1 && visit[nx][ny] == 0) {
                    que.add(Pair(nx, ny))
                    visit[nx][ny] = 1
                }
            }
        }
    }
}