[백준] 11060 - 점프 점프

1. 문제

11060번: 점프 점프

2. 개요

각 칸에 정수가 쓰여진 1 x N의 미로가 있다.

각 칸에서는 미로에 쓰여진 수 이하만큼 점프해서 오른쪽으로 이동이 가능하다.

미로의 길이, 각 칸의 숫자가 주어졌을 때, 가장 오른쪽으로 가는 데 필요한 최소 시간을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 방문확인 및 소요시간을 표시할 visited배열을 만들어둔다.

가장 마지막 칸에 방문하지 못했을 시 -1을 출력해야하므로 모든 칸을 -1로 초기화해둔다.

또한 항상 첫번째 칸에서 출발하므로 0번 인덱스는 0으로 만들어둔다.

0을 큐에 넣고 BFS를 실행한 뒤 답을 출력한다.

3-2. Python

import sys
from collections import deque

N = int(sys.stdin.readline())

visited = [-1 for i in range(N)]
nums = list(map(int, sys.stdin.readline().split()))

q = deque([0])
visited[0] = 0

while q:
    nowX = q.popleft()

    for i in range(1, nums[nowX] + 1):
        nextX = nowX + i

        if nextX >= N:
            continue

        if visited[nextX] != -1:
            continue

        q.append(nextX)
        visited[nextX] = visited[nowX] + 1

print(visited[-1])

3-3. C#

namespace boj_11060
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int N = int.Parse(sr.ReadLine());

            int[] visited = new int[N];
            Array.Fill(visited, -1);

            int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            Queue<int> q = new(new int[] { 0 });
            visited[0] = 0;

            while (q.Count > 0)
            {
                int nowX = q.Dequeue();

                for (int i = 0; i < nums[nowX] + 1; i++)
                {
                    int nextX = nowX + i;

                    if (nextX >= N)
                        continue;

                    if (visited[nextX] != -1)
                        continue;

                    q.Enqueue(nextX);
                    visited[nextX] = visited[nowX] + 1;
                }
            }

            sw.WriteLine(visited[^1]);
            sw.Close();
        }
    }
}