백준 13913 숨바꼭질 4 Kotlin (bfs)

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

13913번: 숨바꼭질 4

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

비슷한 문제

• 1697번. 숨바꼭질
• 12851번. 숨바꼭질 2
• 13549번. 숨바꼭질 3

알고리즘 분류

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

풀이

2021.03.31 - [알고리즘 문제 풀이/백준] - 백준 1697 숨바꼭질 c++

2021.08.03 - [알고리즘 문제 풀이/백준] - 백준 13549 숨바꼭질 3 c++ (다익스트라)

숨바꼭질 시리즈다.

전에는 c++로 풀었구나

지금 보니 좋은 시리즈인 것 같다.

다익스트라, bfs, dp 등등 익힐 수 있다.

 

이번 숨바꼭질 4 문제는 가중치는 1로 다 같고, 최단 시간을 구해야 한다.

여기서 추가된 건 수빈이가 동생을 찾기 위해 최단 시간으로 지나온 길들을 출력해야 하는 점이다.

그래프 탐색에 응용 문제는 항상 이런 output을 추가시키더라.

다행히 이 문제에선 어렵지 않다.

 

문제에 스페셜 저지 딱지가 붙어있다.

예제1, 2를 보면 두 개가 입력이 같은데 결과가 다르다.

둘 중 하나만 출력하면 맞다는 뜻이다.

본인의 코드는 5 4 8 16 17이 나오는데 처음에 예제 2를 보지 못하고 10분 정도 디버깅 했다.

언제쯤 문제 좀 잘 읽을래??????

 

무튼 문제 풀이는 다음과 같다.

- 일반적인 bfs다. 주어진 3가지 동작으로 다음 노드를 구하자.

- 최단 시간은 그냥 bfs돌리면 나온다.

- 우리는 지나온 길을 구해야 한다.

- 방문 체크 배열을 boolean이 아닌 Int로 만들어, visisted[next]에 cur을 삽입, 즉 이전 노드를 삽입한다.

- 수빈이가 동생을 찾았을 때 (next==k) bfs를 종료하고, visited[k]부터 n이 나올 때 까지
visited[k]를 배열에 추가한다.

- 이렇게 배열에 추가하는 이유는 k부터 n까지의 경로를  뽑아 n부터 k까지의 경로를 출력해야 하기 때문이다.

- 배열로 하든 StringBuffer로 하든 상관 없을 것 같다.

- n==k인 경우를 조심하자. 

코드

import java.util.*

val br = System.`in`.bufferedReader()

const val MAX = 200001
val visited = IntArray(MAX){-1}
val dir = arrayOf(1,-1)
fun bfs(n: Int, k: Int): Int{
    val q: Queue<Int> = LinkedList()
    q.add(n)
    var time=0
    if(n==k) return 0
    while(q.isNotEmpty()){
        val size = q.size
        for(i in 0 until size){
            val cur = q.poll()
           for(j in 0 until 3){
               var next = -1
               if(j==2){
                   next = cur* 2
               }
               else {
                   next = cur + dir[j]
               }
               if(next==k){
                   visited[next] = cur
                   return time+1
               }

               if(next !in 0 until MAX) continue
               if(visited[next]!=-1) continue
               visited[next] = cur
               q.add(next)
           }
        }
        time++
    }
    return 0
}

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

    //input
    var (n,k) = br.readLine().split(' ').map{it.toInt()}

    //solve, output
    write("${bfs(n,k)}\n")

    var answerArr = ArrayList<Int>()
    answerArr.add(k)
    if(n!=k) {
        while (true) {
            answerArr.add(visited[k])
            k = visited[k]
            if (k == n || k == -1) break
        }
    }
    for(i in answerArr.size-1 downTo 0 step 1){
        write("${answerArr[i]} ")
    }
    close()
}