코딩테스트를 위한 기본 개념 2탄 - DFS / BFS

 

목차

 

 

https://login-data.tistory.com/24

코딩테스트를 위한 기본 개념 1탄 - 그래프(Graph)

그래프 글에서 이어지는 내용으로, 그래프를 어떻게 탐색하는가 방법에 따른 DFS와 BFS를 정리해보려 한다.

DFS와 BFS 각각 방법으로 탐색하는 순서를 비교하기 위해 아래와 같은 그래프가 있다고 하자.

 

그래프 예시

 

1. DFS (Depth-First Search) : 깊이 우선 탐색

영문에서도 알 수 있는 것처럼, DFS는 그래프에서 깊은 부분(자식노드)을 우선적으로 탐색하는 알고리즘이다. 즉, 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회하는 방법이다. 모든 노드를 방문해야 하거나, 경로의 특징을 저장해둬야 하는 문제 등에서 사용할 수 있다.

 

예시 그래프를 통해 노드 A부터 시작하는 DFS를 실행하면 아래와 같은 순서로 탐색을 진행한다.

DFS : A → B  → D  → E  → F  → C  → G  → H  → I  → J

 

 

1.1 장단점

• 장점 : 현 경로 상의 노드들만 기억하면 되기 때문에 저장공간이 비교적 적게 필요하고, 목표 노드가 깊은 단계에 있을 경우 빠르게 해를 구할 수 있음
• 단점 : 해가 없는 경로가 깊을 경우 탐색 시간이 오래 걸리고, 얻어진 해가 최단 경로가 된다는 보장이 없음. 깊이가 무한히 깊어지면 스택오버플로우가 날 수 있기 때문에 깊이 제한을 둬야 함

 

1.2 시간 복잡도

그래프 구현 방법에 따라 달라진다. (N : 정점의 수, E : 간선의 수)

• 인접행렬에서의 시간 복잡도 
  • 모든 정점을 다 찾아봐야 하기 때문에 dfs(x)의 시간 복잡도 : O(N)
  • dfs(x) 가 N번 호출 ⇒ 전체 알고리즘의 시간 복잡도 : O(N*N) = O(N^2)
• 인접리스트에서의 시간 복잡도
  • 인접행렬과 마찬가지로 dfs(x) 의 시간 복잡도는 O(N), dfx(x)를 N번 호출
  • 전체 알고리즘의 시간 복잡도 : O(N+E)

 

1.3 구현 (with 파이썬)

DFS는 자료구조인 스택과 큐를 사용해서 구현하거나 재귀함수를 통해 구현할 수 있다.

 

1) 인접리스트 - 자료구조 스택과 큐를 활용한 구현

# 그래프는 만들어져 있다고 가정
visited = [False]*(n+1)

def dfs(graph, i, visited) :
    stack = [i]
    visited[i] = True # 방문 처리
    while stack :
        value = stack.pop()
        if not visited[value] :
            print(value, end = ' ')
            visited[value] = True
        for j in graph[value] :
            if not visited[j] :
                stack.append(j)

dfs(graph, v, visited)

 

2) 인접리스트 - 재귀함수를 활용한 구현

# 그래프는 만들어져 있다고 가정
visited = [False] * (n+1)

def dfs(graph, node, visited) :
    visited[node] = True # 방문처리
    print(node, end=' ')
    for j in graph[node] :
        # 자식 노드 순환
        if not visited[j] :
            dfs(graph, j, visited)

dfs(graph, v, visited)

 

3) 인접행렬 - 재귀함수를 활용해 구현

# 그래프는 만들어져 있다고 가정
visited = [False] * (n+1)

def dfs(matrix, i, visited) :
    visited[i] = True
    print(i, end=' ')
    for c in range(n+1) :
        if matrix[i][c] == 1 and not visited[c] :
            dfs(matrix, c, visited)

dfs(matrix, v, visited)

 

 

 

2. BFS (Breadth-First Search)

BFS는 정점들과 같은 레벨에 있는 노드(형제노드)들을 먼저 탐색하는 방식이다. 최단 거리를 구해야 할 경우 사용한다.

bfs : A - B - C - D - G - H - I - E - F - J

 

1.1 장단점

• 장점 : 너비를 우선으로 탐색하기 때문에 경로가 여러 개인 경우에도 최단 경로를 얻을 수 있고, 경로가 무한히 깊어져도 최단 경로를 반드시 찾을 수 있음. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리함
• 단점 : DFS와 달리 큐를 사용해 다음에 탐색할 노드들을 일단 저장하기 때문에 더 큰 저장공간이 필요함

 

1.2 시간 복잡도

DFS와 동일하다.

 

1.3 파이썬으로 구현하기

1) 인접 리스트 - 자료구조 큐 활용한 구현

# 그래프는 만들어져 있다고 가정
visited = [False] * (n+1)

from collections import deque

def bfs(graph, i, visited) :
    queue = deque([i])
    
    while queue:
        value = queue.popleft()
        
        if not visited[value]:
            print(value, end=' ')
            visited[value] = True
            for j in graph[value] :
                queue.append(j)

bfs(graph, v, visited)

 

2) 인접행렬 - 자료구조 큐 활용한 구현

# 그래프는 만들어져 있다고 가정
visited = [False] * (n+1)

from collections import deque

def bfs(matrix, i, visited) :
    queue = deque()
    queue.append(i)
    while queue:
        value = queue.popleft()
        if not visited[value]:
            print(value, end=' ')
            visited[value = True
            for c in range(n+1):
                if matrix[value][c] == 1 and not visited[c] :
                    queue.append(c)