99클럽 코테 스터디 19일차 TIL + BFS

문제

Baekjoon 28069: 김밥천국의 계단

• 설명: 2가지 행동 중 하나를 선택해서 K번 행동하여 N번째 계단에 도달할 수 있는지 판단하여라

풀이

• $0$번째 계단에서 지팡이를 두드리면 $0 + \lfloor \frac{0}{2} \rfloor = 0$이므로 제자리 걸음을할 수 있다.
• 기본적으로 $0$번째 계단에서 BFS를 통해 모든 계단까지의 최단거리를 구할 수 있다.
• 이때 N번째 계단에 도달하기 위한 최소 행동이 A라면, A - K만큼 $0$번째 계단에서 제자리 걸음한 후 이동한다면 무조건 K번째 행동에 N번째 계단에 도달할 수 있다.
• 하지만 만약 A가 K보다 크다면 최단 행동으로도 K번째에 도달하지 못한다는 뜻이므로 이 경우 우리는 김밥을 먹을 수 없다.

오늘의 회고

• 가장 기본적인 BFS 문제인 것 처럼 보이지만, 정확히 K번째에 도달해야하므로 쉽사리 풀지 못하고 헤맸었다.
• 하지만 결국 최단경로로 움직이기 전에 제자리걸음을 하면 K번째에 도달할 수 있다는 것을 깨닫고 바로 구현에 들어갔다.
• 한개의 조건만으로 기존 문제를 아주 잘 응용한 문제인 것 같아 재밌게 풀었다. 좋은 문제다.

Code

# Baekjoon28069.py
from collections import deque

n, k = map(int, input().split())

q = deque()
visited = [False for _ in range(n + 1)]

q.append((0, 0))
visited[0] = True
while q:
    vertex, distance = q.popleft()

    if vertex == n:
        ans = distance
        break

    next_v = vertex + 1
    if next_v <= n and not visited[next_v]:
        visited[next_v] = True
        q.append((next_v, distance + 1))

    next_v = vertex + vertex // 2
    if next_v <= n and not visited[next_v]:
        visited[next_v] = True
        q.append((next_v, distance + 1))

print("minigimbob" if ans <= k else "water")