송아지 찾기 (BFS)
생성일: 2022년 2월 14일 오후 3:45
구현 코드 ⭐
# 송아지 찾기 (BFS)
import sys
from collections import deque
#sys.stdin = open("input.txt", "rt")
def BFS():
while dQ:
now = dQ.popleft()
if now == e:
break
for next in (now-1, now+1, now+5):
if 0 < next <= MAX:
if ch[next] == 0:
dQ.append(next)
ch[next] = 1
dis[next] = dis[now] + 1
print(dis[e])
if __name__ == "__main__":
s, e = map(int, input().split())
MAX = 10000
ch = [0] * (MAX+1)
dis = [0] * (MAX+1)
ch[s] = 1
dis[s] = 0
dQ = deque()
dQ.append(s)
BFS()
- BFS문제는 큐(queue)를 이용해서 해결한다.
- 상태트리를 그리면 다음과 같다.
위의 상태 트리대로 큐에 한 노드씩 넣어가면서 dequeue하고 연결된 하위 노드를 다시 큐에 넣는 작업을 거친다.
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
횟수 | 2 | 1 | 0 | 1 | 2 | 1 |
위와 같이 배열(dis)을 만들어서 각 노드의 인덱스는 위치를 나타내고 값은 횟수(구해야 하는 최소값)을 나타낸다.
반복문을 통해 노드를 방문하게 되면 해당 노드와 일치하는 인덱스에 접근하여 트리에서의 level값을 넣는다.
이때 중복되는 노드를 재방문하는 것은 비효율적이기 때문에 ch 배열을 만들어서 방문한 노드인지를 체크한다.
Author And Source
이 문제에 관하여(송아지 찾기 (BFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lsj8706/송아지-찾기-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)