[알고리즘] 그래프 탐색 알고리즘 : DFS & BFS / Python 파이썬

그래프 탐색 알고리즘 DFS & BFS

• 탐욕(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
• 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.
• * 코딩테스트에서 자주 등장하는 유형

 

이번 포스트에서는 DFS, BFS에 대해 살펴볼 예정이다.

 

---

 

DFS (Depth-First Search)

 

• DFS는 깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다
• DFS는 스택 자료구조(또는 재귀 함수)를 이용한다
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다
• 최대한 깊게 들어가는 방식으로 동작하기 때문에 스택 자료구조 대신 재귀함수를 이용해 구현

 

 

DFS 소스코드 예제 (위 이미지를 구현하였음)

 

#DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end= ‘ ‘)
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: #인접한 노드가 방문하지 않은 상태라면 재귀함수를 이용하여 방문처리 가능
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [], # 1번 노드부터 시작하는 경우가 많기 때문에 0번 노드는 비워둔다.
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 #기본적으로 모든 노드값을 False로 초기화한 것

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 출력: 1 2 7 6 8 3 4 5

 

 

---

BFS (Breadth-First Search)

 

• BFS는 너비 우선 탐색이라고도 부르며 , 그래프에서 가장 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다
  3. 더 이상 2의 과정을 수행할 수 없을 때 까지 반복한다
• ex) 시작노드인 1로부터 [거리가 1인 노드, 거리가 2인 노드, ...] 와 같은 탐색 순서를 갖는다

인접한 노드 중에서는 값이 작은 노드부터 방문한다고 가정한다.

 

방문 처리한 노드는 큐에서 빼준다.

그리고 방문하지않은 노드를 큐에 삽입하고 방문처리한다.

방문하지 않은 인접노다가 없으면 꺼내고 무시한다.

 

BFS 구현 예제 (위 이미지를 구현하였음)

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=‘ ‘)
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2,3,8], '1번 노드는 2,3,8번 노드와 인접해있다.'
    [1,7], '2번 노드는 1,7번 노드와 인접해있다.'
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

# 출력: 1 2 3 8 7 4 5 6

※ 예시 문제 : [음료수 얼려 먹기, 미로 탈출]

• 연결 요소 찾기(Connected Component) 문제
• BFS는 간선의 비용이 모두 같을 때 최단거리를 탐색하기 위해 사용할 수 있다

 

 

References

- 이것이 코딩테스트다 (이코테 2021 강의 몰아보기) 3. DFS & BFS

https://www.youtube.com/watch?v=7C9RgOcvkvo 

- 알음알음 성장로그 https://hei-jayden.tistory.com/35