본문 바로가기

Develop/코딩인터뷰

[코딩인터뷰] 너비 우선 탐색 Breadth first search (BFS)

반응형

너비 우선 탐색 Breadth first search
https://victorqi.gitbooks.io/swift-algorithm/content/Images/AnimatedExample.gif

너비 우선 탐색 Breadth first search (BFS)

너비 우선 탐색 (BFS) 는 코딩 테스트 출제 빈도가 높은 전략입니다. 그래서 반드시 알고 있어야 하고 문제에 활용 가능할지 판단할 수 있어야 합니다. BFS 는 이름 그대로 너비를 우선하여 탐색하는 전략입니다. 그래프에서 각 노드를 방문하면서 방문한 노드와 연결된 노드들을 큐에 추가하고 빼면서 각 노드를 한 번씩 탐색하게 됩니다. 각 탐색을 진행하면서 문제가 요구하는 정답 찾아 가게 됩니다. BFS 는 전략 특성상 '노드 방문 여부'를 체크하지 않으면 무한 반복에 빠질 위험이 있습니다. 따라서 BFS 로 문제를 풀 때는 노드의 방문 여부를 체크하는 코드가 반드시 필요합니다.

BFS 전략으로 푸는 대표적인 문제 유형

  • 노드 사이 간 거리가 동일한 최단 경로 탐색 문제 (노드 간 거리가 다른 문제는 '다익스트라 알고리즘' 또는 '벨만 포드 알고리즘' 으로 해결해야 합니다.)
  • 특정 거리 내 이웃을 탐색하는 문제
  • 그래프 내 메세지 브로드캐스트 문제

전략 기본 순서

  1. '노드' 클래스를 만든다.
  2. 입력된 데이터를 정리해서 각 노드를 생성하고 연결하여 그래프를 만든다.
  3. 탐색 순서를 기록할 큐 자료 구조를 준비한다.
  4. 노드 방문 여부를 기록할 자료 구조를 준비한다.
  5. 그래프의 시작 노드를 큐에 추가하고 탐색을 시작한다.
  6. 각 탐색마다 탐색 순서가 정의된 큐에서 노드를 꺼낸다.
  7. 방문한 적이 없다면 탐색해서 정답을 찾기 위한 함수를 실행한다.
  8. 노드를 방문했다고 기록한다.
  9. 노드와 연결된 이웃 노드들 중 방문하지 않았던 노드들을 큐에 추가한다.

1 번부터 5 번까지는 탐색 전에 준비하는 과정이고, 6 번부터 9 번까지는 큐와 방문 여부를 바탕으로 탐색을 반복하는 과정입니다.

BFS 전략으로 문제를 풀면 다음과 비슷한 코드를 구현하게 됩니다.

from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.adjacent = []

def visit(node):
    print(node.value)

def dfs(node):
    q = deque(node)
    v = []

    while 0 < len(q):
        n = q.popleft()
        visit(n)
        v.append(n)
        for adj in n.adjacent:
            if adj not in v and adj not in q:
                q.append(adj)

깊이 우선 탐색 (Depth first search, DFS) 과의 차이

깊이 우선 탐색 (Depth first search, DFS)도 그래프 형태의 자료구조를 탐색하는데 '너비' 대신 '깊이'를 우선하여 탐색한다는 점이 다릅니다. 하지만 코드는 그다지 유사하게 만들어 지지 않습니다. BFS 는 큐를 활용하여 탐색을 진행하는 반면, DFS 는 재귀 함수를 활용하여 탐색을 진행하는 부분이 BFS와 DFS 가 두드러지게 차이가 나는 부분입니다.

인접 행렬로 표현된 그래프의 경우

그래프를 표현하는 방법은 크게 두 가지가 있습니다.

  1. 인접 리스트: 노드와 노드의 연결로 표현하는 방법
  2. 인접 행렬: 행렬의 행과 열로 연결을 표현하는 방법

인접 리스트로 표현한 그래프가 일반적으로 사용하기가 무난합니다. 왜냐하면 노드를 추가하고 삭제하기가 인접 행렬에 비해 편하기 때문입니다. 행렬의 경우 크기가 이미 정의되어 있는 구조라, 노드를 추가하게 되면 새로운 행렬을 추가해야만 합니다. 특히 중간에 노드를 추가하기 라도 하면 복잡해지기 시작합니다.

하지만 코딩 테스트 문제의 경우 시간 제약 때문에 그래프의 크기가 변하는 문제가 출제되는 경우도 적고, 행렬로 표현하면 디버깅할 때 보기 편하다는 장점이 있어서 무조건 인접 리스트로 그래프를 만들어 문제를 푸는 것보다는 문제가 제공하는 데이터의 형태에 따라 그래프를 만드는게 좋습니다.

예를 들어 다음과 같이 입력이 주어지는 경우는 인접 리스트가 더 적합할 수 있습니다.

1 2
4 2
2 3
4 5

하지만 다음과 같이 입력이 주어지는 경우라면 인접 행렬이 더 적합할 수 있습니다.

4
0 0 1 1
0 0 0 0
1 0 0 1
1 0 1 0
반응형