[BOJ] 스타트링크 in Python & Kotlin

문제풀러 가기!

엄청 어려운 문제는 아니었습니다. 이 문제의 출제의도를 한마디로 표현하자면

문제에서 주어진 조건을 bfs로 만들 수 있는가?

물론 bfs 말고도 여러 방식으로 문제를 풀 수 있겠지만, 가장 간단하게 접근할 수 있는 방법은 bfs였다고 생각합니다.

그래서 문제의 조건을 잘 캐치한 이후 그 조건을 bfs에 반영해주면 됩니다.

문제의 조건은

1. 최대 건물 높이 (F)
2. 최저 건물 높이 (1)
3. 시작 층 높이 (S)
4. 목표 층 높이 (G)
5. 위층으로 향하는 일정한 간격 (U)
6. 아래층으로 향하는 일정한 간격 (D)

으로 주어졌고 최대 높이는 1,000,000까지 입니다. 즉 최대 시간복잡도는 1,000,000으로 생각하고 가는 것이 제일 좋습니다.

그럼 1,000,000까지 있는데, 왜 bfs인가?

사실 갈 수 있는 경로는 2가지로, 특정 층에서 U과 D를 모두 사용하여 너비 우선 탐색을 진행하기 때문에 2^1,000,000까지 되는거 아니야? 라고 생각할 수 있으나 특정 층에서 다른 층으로 갈 수 있는 방법은 문제의 조건 상 항상 고정되어 있고 루프를 돌면서 가는건 최소로 움직여서 가는 방법이 아니므로 방문 여부를 체크하면서 bfs를 사용하면 충분히 1초 100,000,000 연산을 피할 수 있습니다. 결국 최대 1,000,000 연산 안에 문제를 풀 수 있다는 것입니다.

아래는 파이썬 풀이입니다.

import sys
from collections import deque
input = sys.stdin.readline

F, S, G, U, D = map(int, input().split())
visited = [False for _ in range(F+1)]

def bfs(now):
    q = deque([])
    q.append((now, 0))
    while q:
        stair, count = q.popleft()
        
        if stair == G:
            return count

        if stair + U <= F:
            if not visited[stair + U]:
                visited[stair + U] = True
                q.append((stair + U, count + 1))
        if 1 <= stair - D:
            if not visited[stair - D]:
                visited[stair - D] = True
                q.append((stair - D, count + 1))

    return "use the stairs"     

print(bfs(S))

아래는 코틀린 풀이입니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private lateinit var visited: BooleanArray

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (F, S, G, U, D) = readLine().split(" ").map { it.toInt() }
    visited = BooleanArray(F+1) { false }
    when (val answer = canGoToStartLink(U, D, S, G, F)) {
        -1 -> println("use the stairs")
        else -> println(answer)
    }
    close()
}

fun canGoToStartLink(up: Int, down: Int, start: Int, gone: Int, end: Int): Int {
    var queue: Queue<NowLoc> = LinkedList()
    queue.add(NowLoc(start, 0))
    visited[start] = true

    while (queue.isNotEmpty()) {
        var stair = queue.peek().stair
        var count = queue.peek().count
        queue.poll()

        if (stair == gone) return count

        if (stair + up <= end) {
            if (!visited[stair + up]) {
                queue.add(NowLoc(stair + up, count + 1))
                visited[stair + up] = true
            }
        }

        if (stair - down >= 1) {
            if (!visited[stair - down]) {
                queue.add(NowLoc(stair - down, count + 1))
                visited[stair - down] = true
            }
        }
    }
    return -1
}

data class NowLoc(val stair: Int, val count: Int)