[Kotlin] BOJ1103 게임

DFS 와 DP 를 이용해서 풀었던 문제

DFS는 금방 구현을 했는데 DP를 사용하지 않고 그냥 생으로 DFS를 돌리면 시간초과가 나와서 

DP를 어떻게 사용해먹을까 엄청 고민했다..

 

DP를 사용하지 않으면 시간초과가 나오는 이유:

한 좌표에 도달하는 방법은 여러가지가 존재하는데 그 좌표에 도달했을때마다 재귀를 돌려서

하기에는 중복된 값이 너무 많기 때문

 

대략적인 DP 구조 : 

최초 1회 방문에 한해서 방문했을 때의 count값을 dp에 저장해두고

dp에 저장된 값보다 쌓아온 count 값이 작다면 생략하고 크다면 새롭게 갱신하는 방식으로 작동

(생략하는 이유는 지금 까지 쌓아온 count가 dp에 저장된 값보다 작다면 이전 회차보다 큰 최댓값은

갱신할 수 없기 때문)

만약 시간초과가 나와서 골머리를 앓고 있다면 질문게시판의 아래의 답변을 읽어보자.

(https://www.acmicpc.net/board/view/82361)

글 읽기 - [C++] 게시판 반례 모두 해결되나 시간초과 발생, 이유를 알려주시면 감사합니다

 

문제 링크 : https://www.acmicpc.net/problem/1103

1103번: 게임

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
import java.util.StringTokenizer

val MX = arrayOf(0,0,-1,1)//상하좌우
val MY = arrayOf(1,-1,0,0)//상하좌우
var N = 0; var M = 0
lateinit var map : Array<List<Char>>
lateinit var isVisited : Array<Array<Boolean>>
var answer = 0
var isInfinity = false
lateinit var dp :Array<Array<Int>>
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt();  M = st.nextToken().toInt() //N,M (1~50)
    map = Array(N){br.readLine().toList()}
    isVisited = Array(N){Array(M){false}}
    dp = Array(N){Array(M){0}}

    dfs(0,0,1)

    if (isInfinity == false) println(answer)
    else println(-1)
}

fun dfs(y :Int,
        x :Int,
        moveCount : Int){
    val currentValue = map[y][x].digitToInt()
    //체크인
    dp[y][x] = moveCount
    isVisited[y][x] = true
    //연결된 곳 순회
    for (i in 0..3){
        if (isInfinity == true) return

        val nextY = y + (MY[i] * currentValue); val nextX = x + (MX[i] * currentValue)
        //갈 수 있는가? 맵안, H가 아닌곳
        if((nextY !in 0 until N) || (nextX !in 0 until M) || map[nextY][nextX] == 'H'){
            if (answer < moveCount) answer = moveCount
            continue
        }
        //간다.
        if (isVisited[nextY][nextX] == false){
            if(dp[nextY][nextX] > moveCount) continue
            else{
                dfs(nextY,nextX,moveCount + 1)
            }
        //이미 밟았던 곳이라면 무한가능
        }else{
            isInfinity = true
            return
        }
    }
    //체크아웃
    isVisited[y][x] = false
}