[BOJ] 스타트링크 in Python & Kotlin
엄청 어려운 문제는 아니었습니다. 이 문제의 출제의도를 한마디로 표현하자면
문제에서 주어진 조건을 bfs로 만들 수 있는가?
물론 bfs 말고도 여러 방식으로 문제를 풀 수 있겠지만, 가장 간단하게 접근할 수 있는 방법은 bfs였다고 생각합니다.
그래서 문제의 조건을 잘 캐치한 이후 그 조건을 bfs에 반영해주면 됩니다.
문제의 조건은
- 최대 건물 높이 (F)
- 최저 건물 높이 (1)
- 시작 층 높이 (S)
- 목표 층 높이 (G)
- 위층으로 향하는 일정한 간격 (U)
- 아래층으로 향하는 일정한 간격 (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)
Author And Source
이 문제에 관하여([BOJ] 스타트링크 in Python & Kotlin), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dev-junku/BOJ-스타트링크-in-Python-Kotlin저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)