BOJ_16928_뱀과 사다리 게임

문제

풀이

package solve_16928

import java.io.StreamTokenizer
import java.util.*
import kotlin.collections.HashMap

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val snake = HashMap<Int, Int>()
    val ladder = HashMap<Int, Int>()
    val n = input()
    val m = input()

    val map = IntArray(101)

    repeat(n) {
        ladder[input()] = input()
    }

    repeat(m){
        snake[input()] = input()
    }

    val queue : Queue<Node> = LinkedList()

    queue.add(Node(1,0))
    var findFlag = false
    while(queue.isNotEmpty() && findFlag.not()) {
        val (num,depth) = queue.poll()

        for(i in 1..6){
            var newNum = num+i
            if(newNum in snake.keys){
               newNum = snake[newNum]!!
            } else if(newNum in ladder.keys){
                newNum = ladder[newNum]!!
            }
            if(map[newNum] == 0){
                map[newNum] = depth + 1
                if(newNum == 100){
                    findFlag = true
                    break
                }
                queue.add(Node(newNum,depth+1))
            }
        }
    }

    println(map[100])
}

private data class Node(val num: Int, val depth: Int)

사용 알고리즘

BFS, 해쉬

크게 의미 없을것 같긴 하지만 뱀과 사다리의 해쉬맵을 구분하였다 조금이라도 시간을 줄일수 있을 것 같았다.

우선 큰틀은 bfs였다. 결국 1번에서 100번 까지 가기위한 최단 경로였으니 같은 깊이에서 주사위를 굴려 1~6까지의 범위 만큼 더 간 상태에서 해당 위치가 뱀 또는 사다리인지 확인하고 경우에 맞게 다시 이동하였다.
이전에 도착한 점이라면 깊이가 0이 아닐 것이므로 map의 값을 갱신해 나가며 visited를 대신했다. 중간에 가지치기를 위해 100에 도달할 경우 flag를 두어 먼저 빠져 나올 수 있도록 하였다.