프로그램

[파이썬] 문제 : bfs 코드 해석

오디세이99 2023. 1. 7. 18:15
728x90
반응형

파이썬 코드해석

교재의 그림을 보고 리스트를 보세요.

adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1],

[5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]

adj_list[0]을 보면 [2,1] 입니다. 그림에서 보면 0번에 연결된 것이 2, 1 입니다.

이와 같이 인덱스번호로 연결된 인덱스들을 리스트로 만든 것입니다.

​

BFS는 가로축으로 찾아간다고 보면 됩니다. 결과를 보면 처음에 0, 그리고 다음에 2, 1, 그 다음에 3

그 다음 8,9와 같이 진행됩니다.

​

이를 구현하는 코드인 것입니다. queue(큐)라는 자료 구조로 bfs를 구현 합니다.

adj_list = [[2, 1],  [3, 0], [3, 0], [9, 8, 2, 1],       # 위 그림을 보면 0번은 2, 1번과 연결괴어 있습니다. 인덱스 0번이 2,1번 연결 표시
           [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]     # 그러한 연결을 리스트로 만든 것임

n = len(adj_list)                         # 10. adj_list의 요소 갯수
visited = [False for _ in range(n+1)]   # visited = [False, False...False]. 10개의 False기 있는 리스트

def bfs(v):                 # BFS (Breadth-First Search) : 너비 우선 탐색
    queue = []              # 큐라는 자료구조 사용. 먼저 넣은 자료 먼저 사용 구조
    visited[v] = True       # visited 리스트의 v 인덱스 값을 True 함. 방문했다고 표시
    queue.append(v)          # 큐 리스트에 인덱스 v 를 추가
    while len(queue) != 0:         # 큐 리스트에 요소가 있으면 계속 반복
        u = queue.pop(0)            # pop은 인덱스 0 의 값을 리턴하고, 해당 요소가 삭제 됨.
        print(u, ' ',end='')        # 출력. 방문순서를 출력하게 됨.
        for w in adj_list[u]:      # adj_list의 u 인덱스 요소. 즉 [2,1] 또는 [3,0]과 같이 됨
            if not visited[w]:     # visited[w]가 False 면 이라는 뜻. 즉 방문하지 않았으면이 됨.
                visited[w] = True  # 방문으로 표시
                queue.append(w)     # 큐 리스트에 인덱스 w 를 추가. while부터 여기까지가 반복 됨.
    
print('BFS 방문 순서:')
for i in range(n):          # adj_list 의 요소수 만큰 반복
    if not visited[i]:      # visited[i]가 False 이면, 즉 방문하지 않았으면 이 됨.
        bfs(i)               # bfs 험수 실행

결과

간략하게

bfs(0) 으로 한다고 봅시다.

그럼 visited[0] = True가 되고,

while len(queue) != 0:에서는 queue에 0 이 들어가 있으니 반복문 실행되겠죠.

queue.pop(0)이 되면서 queue는 비게 되고, u는 0이 되겠죠.

이를 출력하고, for 문에서 adj_list[u 즉 0]이 되면 w 는 [2, 1]이 순자적으로 나오겠죠.

if not visited[2]: 에서 visited[2] = False인 상태이 그 아래 라인에서 visited[2] = True 가 되고 queue에 2가 추가 됩니다. 다시 for의 w가 1이 되죠. if not visited[1]:도 방문한 적이 없으니 실행되어 그 아래 라인 visited[1] = True가 되고, queue에 추가 되겠죠.

이후 while문으로 되돌아 오면 queue에 2,1 이 있으니 반복문 실행....

이렇게 계속 됩니다.

728x90
반응형