[파이썬/python] 백준 - 28069 김밥천국의 계단

문제

https://www.acmicpc.net/problem/28069

---

문제 설명

1. 문 앞에 무한히 많은 계단이 있다.
   1. 가장 아래 계단의 번호는 0번이며, 위로 올라가면서 순서대로 번호가 붙는다.
   2. 그 중 N번째 계단에 도달해야 한다.
2. 민희는 매번 2가지 행동 중 하나를 선택해서 총 K번 행동할 수 있다. 정확히 K번째 행동에서 N번째 계단에 도달해야 한다.
   1. 계단을 한 칸 올라간다.
   2. 지팡이를 두드려 $i + \lfloor i/2 \rfloor$ 번째 계단으로 순간이동한다.
3. 민희는 0번째 계단에 있을 때, N번째 계단에 도달할 수 있는지 구한다.

 

---

풀이

민희는 0번째 계단부터 순차적으로 계단을 오른다. 따라서 이전 값을 재사용하는 DP 알고리즘이 떠올랐지만, BFS가 더 구현이 쉬울 것 같아 BFS를 사용했다.

보통 1차원이면 BFS를 잘 떠올리기 힘들다. 하지만 몇몇 문제들이 1차원 BFS로 나오니 이 부분을 좀 더 유의하고 있으면 좋을 것 같다고 생각했다.

1. queue에 최초의 위치 0과 횟수 0을 초기화한다.
2. i+1, i + i //2 위치를 탐색하면서 BFS를 진행한다.
   1. 만약 횟수가 K를 넘었다면 해당 위치에서는 탐색을 종료한다.
   2. N에 도달했다면 결과를 반환한다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline
MAX_SIZE = 10**6
n,k = map(int,input().split())

def bfs():
    queue = deque([(0,0)])
    visited = [0 for _ in range(n+1)]
    visited[0] = 1

    while queue:
        i,cnt = queue.popleft()
        if i == n:
            return "minigimbob"
        if cnt == k:
            continue
        for ni in [i+1,i+(i//2)]:
            if ni > n or visited[ni]:
                continue
            queue.append((ni, cnt+1))
            visited[ni] = 1
    return "water"

print(bfs())

---

시간복잡도

• 최악의 경우는 모든 노드의 위치를 탐색하는 경우이다. 즉 $N*2(간선의 개수)$정도의 연산이 필요하다.
• $N = 10^6$이므로 약 $O(10^6)$의 시간복잡도를 가진다.