[백준] 28069 - 김밥천국의 계단

1. 문제

28069번: 김밥천국의 계단

2. 개요

가장 아래 0번 계단부터 출발하여 N번 계단에 위치해 있는 김밥 가게에 가려고 한다.

한 번에 다음과 같은 2가지의 행동을 총 K번 까지 할 수 있다.

1. 계단 한 칸을 올라갑니다.
2. 민희가 집에서 가지고 온 지팡이를 계단에 두드립니다. 만약 민희가 $i$ 번째 계단에서 지팡이를 두드리면 $i +\left \lfloor \cfrac{i}{2} \right \rfloor$번째 계단으로 순간이동합니다.

K번 이내에 N번 위치까지 도달 가능하다면 “minigimbab”을, 그렇지 않다면 “water”를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

BFS를 이용한다.

0을 먼저 큐에 넣고 시작한다.

큐가 비거나 목적지의 방문이 확인될때까지 반복문을 돌린다.

반복문은 큐에서 한 원소를 빼내고 이 원소를 현재위치로 잡는다.

현재위치에서 이동 가능한 두 곳을 탐색한다.

만약 이동가능하고, 방문하지 않은 곳이라면 값을 현재위치까지의 행동횟수 + 1로 갱신한다.

반복문을 탈출한 후, 목적지까지의 행동횟수의 값에 따라 답을 출력한다.

3-2. Python

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

dp = [1000001 for i in range(1000001)]
dp[0] = 0

q = deque([0])

while q and dp[N] == 1000001:
    now = q.popleft()

    nxts = [now + 1, now + now // 2]

    for nxt in nxts:
        if nxt > 1000000:
            continue

        if dp[nxt] != 1000001:
            continue

        dp[nxt] = dp[now] + 1
        q.append(nxt)

if dp[N] <= K:
    print("minigimbob")

else:
    print("water")

3-3. C#

namespace boj_28069
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();

            int N = int.Parse(input[0]), K = int.Parse(input[1]);

            int[] dp = new int[1000001];
            Array.Fill(dp, 1000001);
            dp[0] = 0;

            Queue<int> q = new();
            q.Enqueue(0);

            while (q.Count > 0 && dp[N] == 1000001)
            {
                int now = q.Dequeue();
                int[] nxts = new int[] { now + 1, now + now / 2 };

                foreach (int nxt in nxts)
                {
                    if (nxt > 1000000)
                        continue;

                    if (dp[nxt] != 1000001)
                        continue;

                    dp[nxt] = dp[now] + 1;
                    q.Enqueue(nxt);
                }
            }

            if (dp[N] <= K)
                Console.WriteLine("minigimbob");

            else
                Console.WriteLine("water");
        }
    }
}