BFS

너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색(BFS)은 그래프나 트리 자료 구조를 탐색할 때 사용되는 알고리즘 중 하나로, 시작 노드에서 가까운 노드부터 탐색을 시작하는 방식이다. BFS는 가장 가까운 이웃 노드부터 방문하며, 너비(레벨)를 기준으로 탐색한다.

BFS 탐색 과정

위의 과정을 큐가 공백 상태가 될 때 까지 계속한다.
너비 우선 탐색의 특징은 시작 정점으로부터 거리가 가까운 정점의 순서로 탐색을 진행된다는 것이다.
너비우선 탐색은 거리가 d인 정점들을 모두 방문한 다음, 거리가 (d+1)인 정점들을 모두 방문한다. BFS는 모든 가중치가 1일 때, 최단거리를 구하는 알고리즘이다.

BFS 풀이 방법

선택된 시작노드로 queue 초기화
큐가 빌 때까지 다음단계를 반복
큐에서 가장 앞의 노드를 추출
인접 노드 확인 및 자식 노드를 큐에 추가
큐가 비어있을 때까지 반복
결과 반환 또는 작업 수행

  
def bfs(v):
    queue = deque([v])
    bfs_visited[v] = True # bfs에 처음 들어온 node 방문 표시

    while queue:
        node = queue.popleft()
        sys.stdout.write(str(node))
        sys.stdout.write(' ')
        for i in range(1, N+1):
            # 방문하지 않은 노드 and 현재 노드와 연결된 노드
            if not bfs_visited[i] and graph[node][i]:
                queue.append(i)
                bfs_visited[i] = True

위의 코드는 DFS와 BFS의 문제의 bfs 함수 코드이다. 이 문제를 풀어보면 dfs와 bfs의 차이를 좀 더 쉽게 이해할 수 있고, 코드를 이해하기 편하다. 현재까지 내가 bfs 풀이 방법은 이러한데 문제를 더 풀어보고 나중에 정리해봐야겠다.

DFS와 BFS 언제 적용해야 할까?

DFS 사용

1. 탐색 경로 전체를 찾아야 하는 문제

모든 경로를 탐색하고 저장하기에 적합하다. 예를 들어, 그래프에서 모든 경로 찾기, 문자열 패턴 매칭 등에 사용됩니다.

2. 그래프 순회

그래프의 모든 노드를 한 번씩 방문해야 하는 경우에 DFS를 사용한다. 예를 들어, 그래프 순회, 연결 요소 찾기 등에 사용된다.

3. 깊이 제한 탐색

특정 깊이까지만 탐색해야 하는 경우에 유용하다.

4. 재귀로 구현할 때

DFS는 재귀로 구현하기에 적합하다. 따라서 특정 문제에서 재귀적 접근이 자연스럽게 필요한 경우에 유용하다.

BFS 사용

1. 최단 경로 및 최소 비용 문제

BFS는 너비 우선으로 탐색하므로 레벨(깊이) 순서대로 탐색하면서 최단경로 또는 최소 비용을 찾는데 적합하다. 예를 들어 미로 찾기, 가중치 없는 그래프의 최단 경로 등에 사용된다.

2. 모든 가능한 경로 탐색

모든 가능한 경로를 찾아야 하는 문제에 적합하다. 예를 들어, 그래프에서 모든 경로 찾기, 퍼즐 해결 등에 사용된다.

3. 상태 공간 트리

상태 공간 트리를 탐색할 때, 특히 최소 이동, 최소 단계, 최소 변화 등을 찾아야할 때 유용하다.

4. 구간 그래프

넓은 범위에서 답을 찾는 문제에 적합하다. 예를 들어, 그래프의 최대 깊이 탐색 등이 있다.

참고

너비 우선 탐색(BFS)이란