[백준14248] / 점프 점프 - 그래프(BFS)

백준14248

 

푼 날짜 : 2024.08.16

푼 문제 : [14248] / 점프 점프

사용한 언어 : python

 

 

푼 방법 :

너비 우선 탐색으로 접근하였다.

 

한 칸씩 이동하는 다른 문제와 달리 이번 문제는 돌다리의 숫자만큼 좌우로 움직일 수 있으므로 그 숫자를 저장하고 현재 위치에서 빼거나 더하는 방식으로 접근하였다.

 

 

 

코드 :

import sys
from collections import deque

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

graph_ = list(map(int, sys.stdin.readline().split()))
graph_.insert(0, 0) # 문제를 편하게 풀기 위해 index 0 추가

visited = [0 for _ in range(N+1)]
start = int(sys.stdin.readline())

def BFS(graph_, visited, v):
    queue = deque([v])
    visited[v] = 1

    while queue:
        now = queue.popleft()
        num = graph_[now]
        dx = [-num, num] # 돌다리 숫자만큼 좌, 우로 이동하기 위함
        for i in range(2):
            nx = now + dx[i]
            if 0< nx< N+1:
                if not visited[nx]:
                    queue.append(nx)
                    visited[nx] = 1
        
BFS(graph_, visited, start)
print(sum(visited[1:]))

 

 

알고리즘 연속 31일차 진행중!! ٩( *˙0˙*)۶

 

오예

 

 

앞으로도 꾸준히 풀어야지