송아지 찾기 (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 배열을 만들어서 방문한 노드인지를 체크한다.