[백준 1103번] [Kotlin] 게임

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

1103번: 게임

 

난이도 : 골드 2
태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색

 

 

설명

0,0 부터 시작하여 해당 칸에 적힌 숫자만큼 상하좌우 중 한 방향으로 이동한다 했을 때,

최대 몇 번 이동할 수 있는지 구하는 문제입니다.

 

단순히, DFS로 가장 깊은 depth가 어디인지 확인하면 될 것 같았습니다.

네. 아니였습니다.

 

시간초과가 나버렸으니 시간을 단축시킬 수 있는 테크닉이 필요합니다.

DP를 조금 섞어볼 수 있겠네요.

 

DFS를 사용하게 될 경우, 한 번 찾은 경로를 여러 번 다시 탐색할 수 있기 때문에,

해당 좌표(x,y)에서 가능한 최대 이동 횟수(=depth)를 dp[x][y]에 저장해놓고,

dp[x][y] 가 0 보다 크다면 해당 좌표를 이미 탐색한 것이므로 다시 방문할 필요가 없으며,

해당 좌표에서 얼마나 더 이동이 가능한지(=depth = dp[x][y])를 더해주면 됩니다.

 

 

접근방법

1. 방문체크를 할 배열 visited와 각 지점에서의 최대 이동 횟수를 저장할 dp 배열 선언

2. DFS 탐색 시작

2-1. 좌표 (x, y)에서 map[x][y]에 적힌 값 만큼 상하좌우로 탐색 시작

      단, 이동할 좌표(nx, ny)에 대해 dp[nx][ny]가 0보다 크다면 해당 지점을 이미 방문한 것이므로,

      dp[x][y]를 dp[x][y] 자신과 dp[nx][ny] + 1 중 큰 값으로 갱신.

      (dp[nx][ny] + 1인 이유는 x, y 지점의 이동횟수는 nx, ny 지점의 이동횟수 + 1 이기 때문)

2-2. 이미 방문한 곳을 만났다면 (visited[x][y] == true) 사이클이 형성된 그래프이므로,

     무한이 이동이 가능하므로 -1을 출력하고 종료.

3. dp[0][0] + 1 출력

 

 

 

소스코드

import kotlin.system.exitProcess

lateinit var visited: Array<Array<Boolean>>
lateinit var map: Array<Array<Int>>
lateinit var dp: Array<Array<Int>>

val dx = arrayOf(1, -1, 0, 0)
val dy = arrayOf(0, 0, 1, -1)
var n = -1
var m = -1

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

    map = Array(n) { x ->
        val line = readLine()
        Array(m) { y -> if (line[y] == 'H') -1 else line[y].digitToInt() }
    }

    visited = Array(n) { Array(m) { false } }
    visited[0][0] = true
    dp = Array(n) { Array(m) { 0 } }

    dfs(0, 0, 0)

    println(dp[0][0] + 1)
}

fun dfs(x: Int, y: Int, depth: Int) {

    for (i in 0 until 4) {
        val nx = x + dx[i] * map[x][y]
        val ny = y + dy[i] * map[x][y]

        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == -1) continue

        if (visited[nx][ny]) {
            println(-1)
            exitProcess(0)
        }

        visited[nx][ny] = true

        if (dp[nx][ny] == 0) dfs(nx, ny, depth + 1)
        dp[x][y] = maxOf(dp[x][y], dp[nx][ny] + 1)

        visited[nx][ny] = false
    }
}

 

 

 

후기

제가 제일 좋아하는 DFS, BFS 문제와

제가 제일 싫어하는 DP 문제의 환상의 콜라보 문제였습니다.

 

푸는 내내 재밌었네요.