[Python] BFS (너비 우선 탐색) 알고리즘

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) | 김태원 - 인프런

 

BFS는 너비 우선 탐색 알고리즘입니다. DFS처럼 트리 구조를 탐색하는 알고리즘이지만 큐로 구현된다는 점에서 차이가 있습니다.

 

BFS 문제 예시를 하나 들어보겠습니다.

초기 위치값이 5라고 합시다. 여기서 +1, -1, +5 중 하나를 선택해 이동한다고 생각합니다. 그리고 그 다음에도 세 가지 중 하나를 선택해 이동하는 것을 반복합니다. 이동할 때마다 트리의 레벨은 하나씩 증가합니다.

위치가 3이 되려면 최소 몇 번의 이동이 필요할까요?

 

트리로 나타내면 위와 같습니다. +1만큼 이동한 경우, -1만큼 이동한 경우, +5만큼 이동한 경우마다 각각 가지를 뻗습니다.

이 그림을 통해 3이 되려면 최소 두 번의 이동이 필요한 것을 알 수 있습니다.

 

표로 나타내면 다음과 같으며, 5라는 위치는 2번의 이동을 했을 때도 도달할 수 있지만, 이미 간 적 있는 곳이기 때문에 2가 아닌, 그대로 0으로 표기하도록 합니다.

 

큐에는 이렇게 들어가게 됩니다.

 

 

이 문제를 코드로 나타낼 때는 두 가지의 리스트와 큐가 필요합니다.

1. 모든 값이 0으로 초기화된 ch 라는 리스트 (어떤 위치에 도달한 적이 있는지 구별하기 위해 사용)

2. 모든 값이 0으로 초기화된 dis 라는 리스트 (두 번째 표 그림. 거리를 기록하기 위해 사용)

MAX = 10000    # 좌표의 한계점
ch = [0] * (MAX + 1)
dis = [0] * (MAX + 1)

ch[5] = 1    # 체크 리스트
dis[5] = 0    # 거리 기록 리스트

dQ = deque()
dQ.append(5)

while dQ:
    now = dQ.popleft()    # 현재 나의 위치를 나타냄
    if now == 3:    # 3에 도달했다면 반복문 종료
        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[3])