[Joco][백준/BOJ] 17071 번: 숨바꼭질 5 (Kotlin)

[문제]

17071번: 숨바꼭질 5

[깃허브]

GitHub - Dev-Joco/algorithm-kotlin: Algorithm(Kotlin)

 

문제 요약

• 0 ~ 500,000 직선 좌표 위에서 수빈이의 초기 위치 N(0 ≤ N ≤ 500,000), 동생의 초기 위치 K(0 ≤ K ≤ 500,000) 일 때,
• 수빈이는 매 초 (x+1) or (x-1) or (2*x) 만큼 이동
• s초 일 때의 동생의 위치: K + 1 + 2 + ... + s
• 수빈이가 동생을 잡기 위한 최단 시간을 구하라(좌표 범위를 넘어가면 -1)

제한 조건

• 시간 제한: 0.25초
• 메모리 제한: 512MB

 

풀이

• 수빈이를 A, 동생을 B 라고 할 때,
• 매 초마다 A(수빈)의 위치를 BFS로 탐색
• A의 중복 탐색을 방지하기 위해 visited 활용
• (핵심1) A는 앞으로/뒤로를 반복하며 제자리를 맴돌 수 있음
• (핵심2) 만약 B가 도착한 지점이 이전에 A가 방문했던 곳이라면, A는 방문했던 그 시각부터 주변을 맴돌며 B와 만날 수 있음을 의미함
  • But, 그 위치에 B가 도착한 시각이 짝수 초 => A가 방문했던 시각도 짝수 초
  •                         B가 도착한 시각이 홀수 초 => A가 방문했던 시각도 홀수 초 이어야 만날 수 있다.
• (핵심3) 위 문제를 해결하기 위해 visited 를 짝수 초와 홀수 초에 방문한 기록을 2차원 배열로 구분해서 나누어 저장. 

 

import java.util.ArrayDeque

private const val MAX = 500_000
private val RANGE = 0..MAX
private val DX = intArrayOf(-1, 1, 0) // 더하기
private val DM = intArrayOf(1, 1, 2) // 곱하기

fun main() {
    val input = readLine()!!.split(" ")
    val N = input[0].toInt() // 수빈이의 위치(0 ≤ N ≤ 500,000)
    val K = input[1].toInt() // 동생의 위치(0 ≤ K ≤ 500,000)

    solution(N, K).let { println(it) }
}

fun solution(N: Int, K: Int): Int {
    if (N == K) return 0

    // visited[0][n]: 수빈이가 "짝수" 초에 위치 n의 방문 여부
    // visited[1][n]: 수빈이가 "홀수" 초에 위치 n의 방문 여부
    val visited = Array(2) { BooleanArray(MAX + 1) }
    val queue = ArrayDeque<Int>()

    visited[0][N] = true
    queue.offer(N)

    var sec = 0
    var k = K

    while (queue.isNotEmpty()) {
        k += (++sec) // sec 초 후 동생의 위치

        if (k > MAX) // 동생이 범위를 벗어남
            return -1

        for (i in queue.indices) { // 큐의 한 사이클
            val cur = queue.poll()

            for (j in 0 until 3) {
                val next = (cur + DX[j]) * DM[j] // 수빈이의 다음 위치

                if (next !in RANGE || visited[sec % 2][next])
                    continue

                visited[sec % 2][next] = true
                queue.offer(next)
            }
        }

        // 짝수 초에 수빈이가 방문했었던 위치에 짝수 초에 동생이 도착했다면 혹은,
        // 홀수 초에 수빈이가 방문했었떤 위치에 홀수 초에 동생이 도착했다면
        // 현재 동생의 위치(k)에서 최단 시간(sec)에 만날 수 있음
        if (visited[sec % 2][k])
            break
    }

    queue.clear()
    return sec
}