[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-송아지 찾기(BFS:상태트리 탐색)

 

 

• BFS는 너비우선탐색 이다 
• DFS는 깊이를 보는 방향으로 탐색했는데 BFS는 트리에서 하나의 레벨에 있는 노드를 다 먼저 탐색하고 그 후 레벨로 넘어가는 방식이다

 

 

• BFS를 이용하여 문제를 해결할 때는 방문한 곳의 정보를 저장할 Queue를 사용한다. 또한,  이미 방문한 곳은 방문하지 않기 위한 check list도 필요하다 

import sys
from collections import deque
 
# sys.stdin=open("input", "r")
# input=sys.stdin.readline    # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다
# s=input().rstrip()        # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다
 
s, e = map(int, input().split())
MAX = 10000             # 문제에서 거리가 1~10000 이동 가능하다고 하였다
ch = [0] * (MAX+1)      # vertex에 방문했는지 기록하기 위한, 중복을 피하기 위한 check list
dis = [0] * (MAX+1)     # 시작 지점에서 현재의 vertex까지 몇번만에 방문했는지 기록하기 위한 리스트
ch[s] = 1               # 시작 지점은 방문한 거니까 1로 두고 시작
dis[s] = 0              # 시작 지점이니까 0 level
 
que = deque()           # 방문한 vertex의 값을 기록할 queue
que.append(s)
while que:
    cur_pos = que.popleft()
    if cur_pos == e:
        break
    for next in (cur_pos-1, cur_pos+1, cur_pos+5):
        if 1 <= next <= MAX:
            if ch[next]==0:
                que.append(next)
                ch[next]=1
                dis[next]=dis[cur_pos]+1
 
print(dis[e])