[백준 16173번] [Kotlin] 점프왕 쩰리 (Small)

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

16173번: 점프왕 쩰리 (Small)

 

난이도 : 실버 5
태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

오른쪽과 아래쪽. 두 방향으로만 이동할 수 있고, 해당 칸에 있는 숫자만큼만 이동할 수 있습니다.

 

n의 크기가 매우 작아(2 <= n <= 3) 브루트포스로도 충분히 가능하지만,

저는 dfs가 편해서 dfs를 사용해 풀이하였습니다.

 

 

 

소스코드

import java.util.StringTokenizer
import kotlin.system.exitProcess

var n = 0
lateinit var visited: Array<Array<Boolean>>
lateinit var map: Array<Array<Int>>

fun main() {
    val br = System.`in`.bufferedReader()

    n = br.readLine().toInt()
    map = Array(n) { Array(n) { 0 } }
    visited = Array(n) { Array(n) { false } }

    // 값 세팅
    repeat(n) { x ->
        val st = StringTokenizer(br.readLine())
        repeat(n) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }

    visited[0][0] = true
    dfs(0, 0)

    println("Hing")
}

fun dfs(x: Int, y: Int) {
    // 목표점 도살 시 프로그램 종료
    if (x == n - 1 && y == n - 1) {
        println("HaruHaru")
        exitProcess(0)
    }

    // 현재 위치 + 현재 칸 숫자
    val nx = arrayOf(x, x + map[x][y])
    val ny = arrayOf(y + map[x][y], y)

    for (i in 0 until 2) {
        if (nx[i] !in 0 until n || ny[i] !in 0 until n || visited[nx[i]][ny[i]]) continue
        visited[nx[i]][ny[i]] = true
        dfs(nx[i], ny[i])
    }
}

 

 

dfs 탐색을 수행하며 목표점 도달 시 HaruHaru를 출력하고 프로그램을 종료합니다.

 

만약 dfs가 모두 끝났는데도 프로그램이 살아있다면,

목표에 갈 수 있는 경로가 존재하지 않는다는 뜻이므로, Hing을 출력합니다.