Part6.7_완전탐색_깊이,넓이 우선탐색활용_송아지 찾기(BFS)

Eugenius1st·2022년 2월 7일
0

Python_algorithm

목록 보기
51/83

BFS란??

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque
MAX= 100000
ch = [0]* (MAX+1)
dis = [0]* (MAX+1)

n,m = map(int,input().split())

ch[n] = 1
dis[n] = 0
dQ = deque()
dQ.append(n)

while dQ:
    now=dQ.popleft() # 현재 지점 변수에 값저장
    if now == m:
        break
    for next in(now-1, now+1, now+5):
        #이렇게 for문을 돌면 now-1, now+1, now+5 이 값들을 각각 탐색한다. 즉 세가닥으로 뻗는다.
        if 0 < next <= MAX:
            if ch[next] == 0: # 이전에 방문 안했을 때문 check
                dQ.append(next)
                ch[next] = 1
                dis[next] = dis[now]+1
print(dis[m])
profile
최강 프론트엔드 개발자가 되고싶은 안유진 입니다

0개의 댓글