코딩테스트/알고리즘 기초

DFS/BFS :: 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

ggulgood 2022. 4. 23. 23:28

 

DFS(Depth-First Search)

깊이 우선 탐색

  • 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
  • 인접 행렬(Adjacency Matrix): 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
  • 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식, 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
# 인접 리스트 방식 예제

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장 (노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장 (노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장 (노드, 거리)
graph[2].append((0, 5))

print(graph)

 

결과

[[(1, 7)], [(2, 5)], [(0, 7)], [(0, 5)]]

 

DFS 는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.


① 탐색 시작 노드를 스택에 삽입하고 '방문 처리'를 한다.
② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

  • 방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

 

탐색 순서: 1-> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

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 = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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

 

 

 

 

 

BFS(Breadth First Search)

너비 우선 탐색

  • 가까운 노드부터 탐색하는 알고리즘
    • 최대한 멀리 있는 노드를 우선으로 탐색하는 DFS와 반대
  • 선입선출 방식인 큐 자료구조를 이용하는 것이 정석
  • deque 라이브러리를 사용하는 것이 좋음

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

① 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
② 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

탐색 순서: 1-> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

BFS 예제

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 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, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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

 

  DFS BFS
동작 원리 스택 큐
구현 방법 재귀함수 이용 큐 자료구조 이용

 

 

 

출처: [이것이 취업을 위한 코딩 테스트다 with 파이썬] 서적

저작자표시 (새창열림)