[백준 13565번] [Kotlin] 침투

https://www.acmicpc.net/problem/13565

13565번: 침투

 

난이도 : 실버 2
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

 

 

맨 위에서 맨 아래까지 도달할 수 있는지 판단하는 문제입니다.

dfs / bfs를 응용하여 풀 수 있는데요.

맨 위의 모든 점에서 dfs / bfs를 시작하여 최하층에 도달할 수 있다면 성공입니다.

 

<좌측 1번째 통로 탐색>

 

좌측부터 1번째 통로를 탐색한 결과, 벽에 막혀 가지 못합니다.

 

 

<좌측 2번째 통로 탐색>

 

2번째 통로 역시 최하층 도달에 실패했습니다.

 

 

<좌측 3번째 통로 탐색>

 

3번째 통로의 경우 최하층 도달에 성공합니다.

해당 문제의 핵심은, 최상층의 모든 점에서 DFS/BFS를 돌려 최하층에 한 번이라도 도달할 수 있는가 입니다.

 

 

 

소스코드

lateinit var map: Array<CharArray>
lateinit var visited: Array<BooleanArray>
val dx = intArrayOf(0, 0, 1, -1)
val dy = intArrayOf(1, -1, 0, 0)
var n = 0
var m = 0

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

    visited = Array(n) { BooleanArray(m) }
    map = Array(n) { readLine().toCharArray() }

    for (i in 0..<m) {
        if (dfs(0, i)) {
            println("YES")
            return
        }
    }
    println("NO")
}

fun dfs(x: Int, y: Int): Boolean {
    for (i in 0..<4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0..<n || ny !in 0..<m || visited[nx][ny] || map[nx][ny] == '1') continue
        if (nx == n - 1) return true
        visited[nx][ny] = true
        if (dfs(nx, ny)) return true
    }

    return false
}

 

 

코드 자체는 일반적인 DFS와 크게 다르지 않습니다.

다만, 최하층 도달 시 (nx == n-1) true를 반환하며,

dfs의 반환값이 true이면 계속 이전 스택 프레임까지 true를 전달해주는게 포인트입니다.

즉, dfs(i, 0)이 한 번이라도 true를 반환한다면 "YES"를 출력하고 프로그램을 종료합니다.