[백준] 1697 (숨바꼭질)

#1 알고리즘

그래프 - 너비 우선 탐색 (BFS, Breadth-First Search)

bfs 문제다. 왜 bfs일까? 이 문제에서, 어떤 '위치'에서 도출되는 '다음 위치'는 3종류가 존재한다. 그리고 그 '다다음 위치' 또한 그럴 것이다. 이런 식으로 어떤 단계(순서)가 존재하며 그 단계(순서)에 맞게 순회를 해야한다. bfs 또한 그래프의 일종인 트리를 예로 말하자면, 트리의 깊이(= 단계)를 하나하나 정복해나가며 bfs가 수행되지 않는가? 즉, 순회 원리가 서로 같다.

 

#2 여담

내가 직면한 문제를 해결하기 위한 도구(자료구조)가 무엇인지 잘 선택해야 한다. 무엇을 선택하는지로 문제의 체감 난이도가 달라지기 때문이다. 게다가, 어떤 도구를 사용할 지 고민하는 그 과정 자체가 문제 풀이에 도움이 된다. 가령 이 문제에서는 Queue를 사용하면 좋겠다는 생각이 bfs 알고리즘을 떠올리는 데 도움이 됐다.

 

#3 코드 - 코틀린

package org.example.exam1697.ver5

import java.util.*

var n = -1
var k = -1
val locationToTravelTime = Array(100001) { -1 }

fun main() {
    // (1) 입력값 받기
    val nAndK = readln().split(" ")
    n = nAndK[0].toInt()
    k = nAndK[1].toInt()

    // (2) bfs 방식으로 순회
    bfs(n)

    // (3) 출력
    println(locationToTravelTime[k])
}

fun bfs(startLocation: Int) {
    val locationQueue: Queue<Int> = LinkedList()
    val visited = Array(100001) { false }

    locationQueue.add(startLocation)
    visited[startLocation] = true
    locationToTravelTime[startLocation] = 0

    while (locationQueue.isNotEmpty()) {
        val prev = locationQueue.poll()

        for (next in getNextLocations(prev)) {
            if (!visited[next]) {
                locationQueue.add(next)
                visited[next] = true
                locationToTravelTime[next] = locationToTravelTime[prev] + 1
            }
        }
    }
}

fun getNextLocations(old: Int): List<Int> {
    val candidates = listOf(
        old - 1,
        old + 1,
        old * 2
    )

    val nextLocations = ArrayList<Int>()
    for (candidate in candidates) {
        if (candidate in 0..100000) {
            nextLocations.add(candidate)
        }
    }
    return nextLocations
}