너비 우선 탐색 BFS

Effy_ee·2023년 8월 8일
0

코딩테스트

목록 보기
44/118

BFS 알고리즘은 '너비 우선 탐색'이라는 의미를 가진다. 가까운 노드부터 탐색하는 알고리즘이다. DFS는 멀리있는 노드를 우선적으로 탐색하는 방식으로 동작하지만, BFS는 그 반대이다. 시간 복잡도는 O(N) 이다.

BFS 예제

from collections import deque

#BFS 메서드 정의
def dfs(graph,start,visited):
	#큐(Queue)구현을 위해 deque 라이브러리 사용
    queue=deque([start])
    visited[start]=True
    #큐가 빌 때까지 반복
    while queue:
        v=queue.popleft()
        print(v,end='')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
    
    #2차원 리스트 
    ...
    
    visited=[False]*9
    
    #BFS 호출
    bfs(graph,1,visited)

1개의 댓글

comment-user-thumbnail
2023년 8월 8일

글 재미있게 봤습니다.

답글 달기