Today I Learned

오늘은 간만에 릿코드 자바 말고, 백준에서 코틀린으로 코테 문제를 풀어봤다!

숨바꼭질

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

문제

두 지점 N,K (0 ≤ N,K ≤ 100,000)가 주어진다. N을 기준으로 1초동안 +1, -1, x2의 행동 중 하나를 할 수 있다.
N에서 K까지 갈 수 있는 가장 빠른 시간을 반환해라.

ex) 입력 : 5 17 출력 : 4
과정 : 5-10-9-18-17

풀이 과정

1. DP, DFS(재귀) 등 여러 방법이 떠올랐지만 DFS 방식은 너무 많이 활용했기에, 조금 덜 해본 큐 중심의 BFS로 구현을 시작했다.

2. 우선 readln().split(" ").map { it.toInt() }로 한번에 두 변수를 할당받는다. 코틀린은 입출력이 편해서 자바보다 좋게 느껴진다.

3. BFS에서 필수적인 방문 기록 배열을 visited로 만든다.

4. Queue를 만드는데 기록해야할 것이 현재 위치(수)와 시간이므로 Pair 객체를 int,int로해서 만든다.

5. 현재위치 n, 시간 0초로 pair를 만들어 큐에 넣고 bfs를 시작한다. 큐가 비지 않을때 까지 반복문을 돌린다.

6. 큐에서 하나 꺼내서 현재 위치 기준으로 -1, +1, x2를 시도한 후, 그것이 방문도 하지 않았고, 제약범위에 있는 경우에만 큐에 다시 집어 넣는다.

7. 반복문이 도는 동안 현재 위치가 타겟 위치면 시간을 반환하면 완료!

Kotlin Code

import java.util.*

fun main() {
    val (n, k) = readln().split(" ").map { it.toInt() }
    val visited = BooleanArray(100001){false}
    val queue: Queue<Pair<Int, Int>> = LinkedList()

    queue.offer(Pair(n, 0))
    visited[n] = true

    while (queue.isNotEmpty()) {
        val (current, time) = queue.poll()

        if (current == k) {
            println(time)
            break
        }

        val next = listOf(current - 1, current + 1, current * 2)

        for (p in next) {
            if (p in 0..100000 && !visited[p]) {
                queue.offer(Pair(p, time + 1))
                visited[p] = true
            }
        }
    }

}