[백준/BOJ] 1937번: 욕심쟁이 판다

문제

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

1937번: 욕심쟁이 판다

풀이

처음에 문제를 봤을 때  "아 가장 길이가 짧은 곳에서부터 시작하면 되겠구나" 라는 생각을 하였다.

하지만 예시를 보고서는 "어라? 이게 왜 이 값이 나오지?" 하고 보니 꼭 최소 길이부터 시작한다고 가장 많이 간다는 것이 아니었다.

 

쨌든 이 문제를 dfs를 통해 푼다는 것은 변하지 않는다.

여기에 더해 dp를 추가로 이용했는데, 모든 칸을 dfs로 돌리면 시간이 오래 걸려 시간 초과가 발생할 것이라 생각하였다.

우선 dp를 어떻게 사용했는지 다음의 그림을 통해 보자.

위 그림을 대나무숲이라고 보자.

만약 판다가 (2, 2) 즉, 마지막 칸에서 출발한다고 하자.

이 때 판다가 갈 수 있는 최대 길이의 칸은 3 → 6 → 9로 총 3칸이다.

이 3이라는 값을 (2, 2)에 저장해준다.

 

다음으로 판다가 (2, 1)에서부터 출발한다고 하자.

그렇다면 판다가 갈 수 있는 최대 길이의 칸은 2 → 3 → 6 → 9가 된다.

이 때 3에서 출발하여  갈 수 있는 최대 칸은 3칸인 것을 미리 구했으므로, 우리는 (2, 2)의 최대 칸 + 1을 해주면 된다.

즉, dp라는 변수가 있다면, dp[2][1]  = dp[2][2] + 1이 된다.

 

이제 dfs를 통해 탐색을 시작해주면 된다.

만약 탐색을 시작하려는 칸의 값이 0이 아니라면 이미 갈 수 있는 최대 칸을 구해놓은 칸이다.

따라서 그 값을 반환해주면 된다.

 

현재 칸이 아직 최대 길이를 구하지 못했다면, 우선 값을 1로 바꿔준다.(현재 칸에 왔으므로)

이후 4방향을 탐색하며 현재 칸보다 더 긴 대나무가 나온다면 탐색을 이어가고, dp의 값을 갱신해주면 된다.

코드

import kotlin.math.max

private lateinit var bambooForest: Array<IntArray>
private lateinit var dp: Array<IntArray>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var size = 0

fun main() = with(System.`in`.bufferedReader()) {
    size = readLine().toInt()
    bambooForest = Array(size) { IntArray(size) }
    dp = Array(size) { IntArray(size) }

    repeat(size) { i ->
        val bambooLength = readLine().split(" ").map { it.toInt() }
        repeat(size) { j ->
            bambooForest[i][j] = bambooLength[j]
        }
    }

    var answer = 0
    repeat(size) { i ->
        repeat(size) { j ->
            answer = max(answer, bambooSearch(i, j))
        }
    }

    println(answer)
}

private fun bambooSearch(y: Int, x: Int): Int {
    if(dp[y][x] != 0) return dp[y][x]

    dp[y][x] = 1
    repeat(4) { i ->
        val nextY = y + dy[i]
        val nextX = x + dx[i]

        if(!inRange(nextY, nextX)) return@repeat

        if(bambooForest[nextY][nextX] > bambooForest[y][x]) {
            dp[y][x] = max(dp[y][x], bambooSearch(nextY, nextX) + 1)
        }
    }

    return dp[y][x]
}

private fun inRange(y: Int, x: Int): Boolean = y in 0 until size && x in 0 until size