[백준] 1697:숨바꼭질
BFS
- 전형적인 bfs 문제이다
- cnt 를 셀 수 있는 배열을 하나 만든다.
- bfs 조건에 맞으면 1 증가 시킨다.
- 비교 할 것과 목표 값이 같으면 목표값의 배열 값을 출력한다.
index 에러 났음 , pop한 값이 10만 보다 크면 continue
from collections import deque
n, k = map(int, input().split())
dx = [2, 1, -1]
come = [0 for _ in range(200001)]
visited = [False] * 200001
def bfs(x):
queue = deque([x])
visited[x] = True
while queue:
v = queue.popleft()
if v == k:
break
if v > 100001:
continue
for i, h in enumerate(dx):
if i == 0:
nx = v * h
else:
nx = v + h
if nx < 0 or nx > 200001:
continue
if visited[nx] == True:
continue
else:
visited[nx] = True
queue.append(nx)
come[nx] = come[v] + 1
return come[v]
print(bfs(n))
Author And Source
이 문제에 관하여([백준] 1697:숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@jinii/백준-1697숨바꼭질
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
index 에러 났음 , pop한 값이 10만 보다 크면 continue
from collections import deque
n, k = map(int, input().split())
dx = [2, 1, -1]
come = [0 for _ in range(200001)]
visited = [False] * 200001
def bfs(x):
queue = deque([x])
visited[x] = True
while queue:
v = queue.popleft()
if v == k:
break
if v > 100001:
continue
for i, h in enumerate(dx):
if i == 0:
nx = v * h
else:
nx = v + h
if nx < 0 or nx > 200001:
continue
if visited[nx] == True:
continue
else:
visited[nx] = True
queue.append(nx)
come[nx] = come[v] + 1
return come[v]
print(bfs(n))
Author And Source
이 문제에 관하여([백준] 1697:숨바꼭질), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jinii/백준-1697숨바꼭질저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)