[백준 1937] - 욕심쟁이 판다(Kotlin)[골드3]

문제

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

1937번: 욕심쟁이 판다

 

문제 설명

문제 초반에는 단순하게 dfs를 진행해서 최대로 갈 수 있는 칸 수를 기록하면서 진행했다.

골드 3치고 문제가 너무 쉽다고 생각했는데,

34% 정도에서 시간초과가 발생했다.

생각해 보면 당연하다. 최대 배열 크기가 500이고, 500x500을 계속해서 무식하게 탐색하면 시간초과가 나는 건데 왜 이 생각을 못했을까.

 

그렇다면 수정해야 될 것은 탐색을 하는 범위라고 생각했다.

해결방법은 2가지정도로 생각했다.

1. 탐색의 범위를 줄이기
2. 방문처리를 해서 탐색한 지점을 다시 탐색하지 않기

첫 번째 방법은 어느 지점에서 출발할지도 선택해야 하고, 탐색의 범위를 줄이는 것이 불가능하다고 판단했다.

따라서 이미 탐색한 범위를 다시 탐색하지 않는다면 시간을 줄일 수 있을 것이라고 판단했다.

 

이미 탐색함 지점을 다시 탐색하지 않기 위해서 어떻게 해야할까에 대해서 고민을 많이 했다.

방문처리는 다양한 것인데, 이 방문처리를 통해서 어떠한 결과를 이끌어낼까에 대해서 고민을 한 결과

해당 지점에서 최대로 갈 수 있는 칸 수를 기록하면 방문처리도하고, 최종 목표인 최대 지점까지의 결과를 알 수 있을 것이라고 판단했다.

예를 들어서 9를 탐색한다고 가정하자. 

처음 탐색에서 아래방향으로 탐색을 한다고 가정할 시 , 끝까지 탐색을 하고 9에는 3이, 11에는 2가, 15에는 1이 저장될 것이다.

다른 방향을 탐색할 시, 최댓값을 계속해서 갱신한다.

이렇게 하면, 만약 내가 다른지점에서 탐색을 하다가 9,11,15에 도착하면 그때는 이미 구한 값이 있기 때문에 탐색을 진행하지 않고

이미 구한값을 그대로 넣어주면 된다. (DP의 개념과 비슷하다)

자세한 코드는 주석을 참고하시면 됩니다

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
class `1937` {
    val br =BufferedReader(InputStreamReader(System.`in`))
    var size =0
    var answer =0
    private lateinit var graph : Array<Array<Int>>
    private lateinit var accum : Array<Array<Int>>
    val x = arrayOf(1,-1,0,0)
    val y = arrayOf(0,0,1,-1)
    init{
        input()
        search()
        print(answer)
    }
    fun input(){
        size = br.readLine().toInt()
        graph = Array(size, {Array(size, {0})})
        accum = Array(size, {Array(size, {1})})
        for(i in 0 until size){
            val line = br.readLine()
            val token = line.split(" ")
            for(j in 0 until size){
                graph[i][j] = token[j].toInt()
            }
        }
    }
    fun search() : Int{
        for(i in 0 until size){
            for(j in 0 until size){
               answer = max(answer,dfs(i,j))
            }
        }
        return answer
    }
    fun dfs(row : Int, col : Int) : Int{
        val now = graph[row][col]
        if(accum[row][col]!=1) //이미 한번 거친 좌표라면 탐색을 하지 않고 넣어줌.
            return accum[row][col]
        for(dir in 0 until 4){
            val mx = row + x[dir]
            val my = col + y[dir]
            if(mx !in graph.indices || my !in graph.indices) //배열 범위를 벗어날 경우
                continue
            if(now >= graph[mx][my]) //now가 작아야함. 반.드.시
                continue
            accum[row][col] = max(accum[row][col],dfs(mx,my)+1)
        }
        return accum[row][col]
    }
}
fun main(){
    val solution = `1937`()
}