백준 12761 돌다리 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/12761

12761번: 돌다리

문제

동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N번 돌 위에, 주미는 M번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A나 B만큼 좌우로 점프할 수 있으며, 순간적으로 힘을 모아 현 위치의 A배나 B배의 위치로 이동을 할 수 있다. 예를 들어 지금 동규가 7번 돌 위에 있고 스카이 콩콩의 힘이 8이면 그냥 점프를 해서 15번 돌에 갈 수도 있고, 순간적으로 힘을 모아 56번 돌에 갈 수도 있다는 것이다. 주어진 8가지의 방법 중 적절한 방법을 골라서 최대한 빨리 동규가 주미를 만날 수 있게 도와주자. 단, 이동 과정에서 100,000보다 크거나 0보다 작은 번호의 돌은 존재하지 않으므로 갈 수 없고, 같은 방법을 계속 사용해도 되며 항상 도달할 수 있는 케이스만 주어진다.

입력

입력의 첫 줄에 스카이 콩콩의 힘 A와 B, 그리고 동규의 현재위치 N, 주미의 현재 위치 M이 주어진다. (단, 2≤A,B≤30 이고  0≤N,M≤100,000)

 

출력

동규가 주미에게 도달하기 위한 최소한의 이동 횟수를 출력하라.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

간단한 bfs 문제이다.

주어진 8개의 동작으로 모두 bfs 탐색을 하면, 가장 빨리 m에 도착하는 노드의 이동 횟수가 정답이 된다.

실수하기 쉬운 부분은 다음 노드가 돌다리의 범위를 벗어날 때인데, 돌다리의 범위는 0부터 m이 아니라 0부터 100,000이다. 이거 때문에 맞왜틀 시전했다. 나처럼 시간낭비하는 사람 없길

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
val MAX = 100001
val visited = BooleanArray(MAX)

fun move(dir : Int, cur : Int, a : Int, b: Int) : Int{
    return when (dir) {
        0 -> cur+1
        1 -> cur-1
        2 -> cur+a
        3 -> cur-a
        4 -> cur+b
        5 -> cur-b
        6 -> cur*a
        7 -> cur*b
        else -> -1
    }
}

fun bfs(a : Int, b : Int, n : Int, m : Int) : Int{
    if(n==m) return 0
    val q : Queue<Pair<Int,Int>> = LinkedList<Pair<Int,Int>>()
    q.add(Pair(n,0))
    visited[n]=true
    while(q.isNotEmpty()){
        val cur = q.poll()
        for(dir in 0 until 8){
            val next = move(dir,cur.first,a,b)
            if(next !in 0 until MAX) continue
            if(next == m ) return cur.second+1
            if(visited[next]) continue
            visited[next]=true
            q.add(Pair(next,cur.second+1))
        }
    }

    return -1
}

fun main() = with(System.out.bufferedWriter()){

    val (a,b,n,m) = br.readLine().split(' ').map{it.toInt()}

    write("${bfs(a,b,n,m)}")

    close()
}