알고리즘 | 그래프 탐색 | BFS, DFS

앞서 실제 세계를 데이터 구조로 모델링하기 위해 그래프를 사용한다고 했는데, 실제 문제 해결까지 가기 위해서는 표현에 그칠 것이 아니라 다양한 방식의 활용법을 모색할 필요가 있다. 그 중 대표적으로 그래프 내의 정보를 효율적으로 탐색하는 탐색 기법이 빠질 수 없다.

 

그 중에서도 BFS(Breadth-First Search, 너비우선탐색)와 DFS(Depth-First Search, 깊이우선탐색)는 가장 기본적이면서도 널리 사용되는 탐색 알고리즘이다. BFS와 DFS는 그래프의 모든 노드를 방문하는 방법이지만, 방문 순서와 방식에는 큰 차이가 있다. 

 

이 두 알고리즘은 다양한 심화 알고리즘의 핵심 아이디어 기반이 되기도 한다. 기업 코딩테스트에서도 단골로 출제되는 주제이니만큼 제대로 이해하는 것이 좋다. 

---

BFS와 DFS

BFS와 DFS의 동작 원리는 유사하다. 다음 조건과 순서를 만족한다. 

1. 한번 큐 or 스택에 넣었던 노드는 다시 넣지 않는다. 
   • 노드의 방문 여부를 마킹하는 방법 등으로 이를 보장한다.
2. 방문 노드를 꺼내고(출력) -> 자식 노드가 있다면 큐 or 스택에 넣어주기 

 

구체적인 동작 방식, 구현상의 주요 차이점은 다음과 같다.

• BFS는 레벨 별로 탐색한다.
  • 즉, 해당 레벨의 모든 노드를 순회한 후 다음 레벨로 넘어간다. 이를 위해 큐를 활용한다.
• DFS는 가지 별로 탐색한다.
  • 즉, 해당 가지의 모든 레벨을 순회한 후 다음 가지로 넘어간다. 이를 위해 스택 또는 재귀함수를 활용한다.
  • 스택 대신 재귀 호출을 이용하면 코드가 훨씬 간결해진다. 그러나 스택 오버플로우와 같은 문제가 발생 가능하므로, 문제의 규모와 조건에 따라 적절한 방법을 사용해야 한다. 

 

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

핵심 아이디어

그 이름에서도 알 수 있듯이 너비를 우선하여 탐색하는 알고리즘이다. 시작점에서 가장 가까운 노드부터 탐색하며, 같은 레벨의 모든 노드들을 방문한 후에 다음 레벨의 노드들을 방문한다. (레벨은 정점 사이를 연결하는 간선의 수로 판단한다.) 이를 위해 큐를 활용한다. 

 

프림(Prim)의 최소 신장 트리 알고리즘, 다익스트라(Dikstra)의 단일 출발점 최단 경로 알고리즘이 BFS와 비슷한 아이디어를 사용한다. (물론 구체적인 목적과 동작 원리에 차이가 있고, 이들은 우선순위 큐를 활용해서 구현하는 경우가 많다.)

 

알고리즘 동작 원리, 구현 방법

0. 시작: 시작 노드를 큐에 넣는다.
1. 현재 큐의 노드를 꺼내 해당 노드를 방문한다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 큐에 추가
3. 큐가 비어있지 않으면 1번부터 반복

 

 

DFS(Depth-First Search, 깊이우선탐색)

핵심 아이디어

DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 시작 노드에서 시작하여, 다음 가지(branch)로 넘어가기 전에 해당 가지를 완벽하게 탐색하는 방식이다. 이를 미로 찾기에 비유하면, 한 방향으로 갈 수 있을 때까지 계속 가다가 막다른 길에 들어서면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다시 탐색을 이어가는 방식과 유사하다. 

 

위 아이디어를 구현하기 위해 스택(Stack)을 활용하거나 재귀함수를 이용하여 구현한다. 

 

알고리즘 동작 원리, 구현 방법

스택 활용

0. 시작: 시작 노드를 스택에 넣고 방문 처리를 한다.
1. 스택이 비어있지 않는 동안 다음 작업을 반복한다:
   a. 스택의 맨 위 노드를 꺼낸다.
   b. 해당 노드의 인접 노드 중 방문하지 않은 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다.
   c. 모든 인접 노드를 방문했다면, 스택에서 맨 위 노드를 꺼내서 탐색을 계속한다. 

 

재귀 함수 활용

1. 현재 노드를 방문 처리한다. 
2. 현재 노드와 인접한 노드 중 방문하지 않은 노드에 대해 재귀적으로 DFS 함수를 호출

 

DFS와 BFS: 구현

백준 1260번 문제(DFS와 BFS)를 통해 구현 방법을 확인해보자. (https://www.acmicpc.net/problem/1260)

문제: 
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력: 
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력:
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

1. 그래프 표현

들어오는 입력값을 토대로 그래프를 표현하는 것부터 시작해야 한다.

공부가 목적이니 만큼, 직전에 배웠던 1) 인접 리스트법과 2) 인접 행렬법을 하나씩 사용해서 구현해보자. 

 

인접 리스트법

# 그래프 표현 - 1) 인접 리스트
def AdjacencyList(V, E):
    # 리스트 구조 세팅
    graph = {} 
    for i in range(1, V+1):
        graph[i] = []

    # 연결 관계 채우기
    for i in range(E):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    
    # (문제 조건) 오름차순 출력을 위해 인접 노드 정렬하기
    for key in graph:
        graph[key].sort()
    
    return graph

----------------------
# 표현된 그래프 (예제 입력1)
{1: [2, 3, 4], 
 2: [1, 4], 
 3: [1, 4], 
 4: [1, 2, 3]}

 

인접 행렬법

# 그래프 표현 - 2) 인접 행렬
def AdjacencyArray(V, E):
    # 행렬 구조 세팅
    graph = []
    for i in range(V+1): # 정점 번호가 1부터 시작하는 문제 특성상, 편의를 위해 0행과 0열은 비워둠
        graph.append(list(0 for i in range(V+1))) 

    # 연결 관계 채우기
    for i in range(E):
        x, y = map(int, input().split())
        graph[x][y] = 1
        graph[y][x] = 1

    return graph

----------------------
# 표현된 그래프 (예제 입력1)
[[0, 0, 0, 0, 0],
 [0, 0, 1, 1, 1],
 [0, 1, 0, 0, 1],
 [0, 1, 0, 0, 1],
 [0, 1, 1, 1, 0]]

 

2. DFS 구현

마찬가지로 공부가 목적인 만큼, DFS를 스택(Stack)을 이용해서 한 번, 재귀 함수를 이용해서 한 번씩 구현해보자.

DFS 구현(1): 스택 이용

# DFS 구현(1): 스택 활용
def DFS_stack(graph, start):
    # 방문 목록 만들기
    visited = []
    # 시작 노드를 스택에 넣어준다. 
    stack = [start]
    
    # 스택이 비어있지 않는 동안
    while stack:
        node = stack.pop() # 스택의 맨 위 노드를 꺼낸다.

        if node not in visited: # 아직 방문하지 않았다면,
            print(node, end=' ') # 출력
            visited.append(node) # 방문 처리
            stack.extend(sorted(graph[node], reverse=True)) # 인접 노드를 스택에 넣기
            # 오름차순으로 출력하라는 문제 특성상, 스택에는 역으로 넣어줘야 한다.

    return

 

 

DFS 구현(2): 재귀 함수 이용

# DFS 구현(2): 재귀 함수 활용
def DFS_recursion(graph, node, visited):
    print(node, end=' ') # 출력
    visited.append(node) # 방문 처리

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[node]:
        if i not in visited: # 아직 방문하지 않았다면
            DFS_recursion(graph, i, visited)

 

 

dfs 구현 코드에서 경험적으로 알아낸 점:

1. 방문 여부(if문)는 재귀문 처음에 체크해도 되고, 위 코드처럼 인접 노드를 선정하는 과정에서 체크해도 된다.
2. 실행 속도는 후자(for문 안에서 방문여부 체크)가 현저히 빠름
3. 위 코드처럼 visited를 빈 배열로 선언한 후 방문한 노드를 추가하기 보다는,
   boolean 배열로 (ex: [False]*(노드 수+1)) 선언한 후 TRUE/FALSE로 판별하는게 더 빠르다.

 

 

 

3. BFS 구현

# BFS 구현
def BFS(graph, start):
    # 방문 목록 만들기
    visited = []
    # 시작 노드를 큐에 넣어준다.
    que = deque([start]) 

    # 큐가 비어있지 않는 동안
    while que:
        node = que.popleft() # 큐에서 맨 아래 노드를 꺼낸다.
        if node not in visited: # 아직 방문하지 않았다면,
            print(node, end=' ') # 출력
            visited.append(node) # 방문 처리

            for i in graph[node]: # 해당 노드의 인접 노드들에 대해서
                if i not in que: # 아직 큐에 들어가지 않았다면            
                    que.append(i) # 대기 큐에 넣어준다. 

    return

 

 

BFS와 DFS: 비교

항목/알고리즘 BFS (Breadth-First Search) DFS (Depth-First Search)

	BFS (Breadth-First Search)	DFS (Depth-First Search)
탐색 순서	시작 노드에서 가까운 노드부터 방문한다. 모든 인접 노드를 방문한 후, 그 인접 노드들의 인접 노드들을 방문한다.	시작 노드에서 한 쪽 가지의 노드로 깊게 들어가며 방문한다. 더 이상 방문할 노드가 없으면 이전 노드로 돌아와서 다른 노드를 방문한다.
공간 복잡도	DFS보다 많은 메모리를 사용한다. 모든 노드를 큐에 저장해야 하기 때문이다.	BFS보다 일반적으로 더 적은 메모리를 사용한다. 경로상의 노드만 기억하면 된다.
시간 복잡도	모든 정점과 간선을 방문하는 경우 O(V + E)	모든 정점과 간선을 방문하는 경우 O(V + E)
결과의 특성	최단 경로를 보장한다.	최단 경로를 보장하지 않는다.
활용 분야	최단 경로 문제, 네트워크 브로드캐스팅, SNS 친구 추천 등	모든 경로를 탐색해야 하는 문제, 사이클 검출, 연결 요소 찾기, 위상 정렬 등
제약사항	큰 그래프에서는 메모리 문제가 발생할 수 있다.	재귀를 활용할 경우 깊은 그래프에서는 스택 오버플로우가 발생할 수 있다.
특징	동심원처럼 레벨 단위로 탐색한다.	깊게 파고든 후, 다시 돌아와 다른 경로로 깊게 파고든다.

 

 

---

마지막으로 BFS와 DFS의 기본 개념을 이해하는데 큰 도움을 준 유튜브 영상이 있어 공유! (엔지니어 대한민국 이라는 채널)

• https://www.youtube.com/watch?v=_hxFgg7TLZQ