[백준/Python] 14248번(BFS)_점프 점프

📌문제 유형

그래프이론, 그래프 탐색, DFS, BFS (실버2)

 

📌문제

14248번: 점프 점프

 

📌나의 문제풀이

- 틀림

from collections import deque

n = int(input())
num_list = list(map(int,input().split()))
start = int(input())

graph = [[] for _ in range(n+1)] 
for i in range(len(num_list)):
    graph[i+1].append((i+1) - num_list[i] if (i+1) - num_list[i] > 0 else 1)
    graph[i+1].append((i+1) + num_list[i] if (i+1) + num_list[i] < n+1 else n)

visited = [False] * (n+1)

q = deque()
for num in graph[start]:
    q.append((start, num))


# 오류
while q:
    now, next = q.popleft()

    if visited[now] == True or now == next:
      continue

    visited[now] = True
    
    for num in graph[next]:
      if not visited[next]:
        q.append((next, num))
        visited[now] = True
    

ans = 0
for v in visited:
    if v == True:
        ans += 1
print(ans)

 

📌 다른사람의 문제풀이

백준 알고리즘 14248번 점프 점프(python)

from collections import deque

def bfs(node):
    q = deque()
    q.append(node)
    check[node] = 1
    while q:
        node = q.popleft()
        for d in [-graph[node], graph[node]]:
            t = node+d
            if (0 <= t < n) and check[t] == 0:
                q.append(t)
                check[t] = 1

n = int(input())
graph = list(map(int, input().split()))
s = int(input())-1
check = [0]*(n)
bfs(s)
print(check.count(1))

 

📌 리뷰 

- 방문 가능한 거리가 for문으로 움직여야 함

- BFS 코드 익히기 (while q전에 첫 노드 visited = True, 이후 q.append() 시 visited = True)