[알고리즘] 탐색 알고리즘 DFS, BFS

-- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다.

 

1. DFS

• Depth First Search, 깊이 우선 탐색
• 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘
• 주로 스택을 활용하는 방식임
  • 스택 : 후입후출)
• 동작방식
  1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
  2. 스택의 최 상단 노드에 방문하지 않은 인접노드가 있다면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
• 동작방식을 아래 그래프를 예시로 살펴보자.

그래프 예시

• 마지막에 "스택이 들어간 순서" 를 한데 모아보면, 1,2,7,6,8,3,4,5 가 된다.

 

▶  DFS를 코드로 구현해보기

• 위와 동일한 그래프를 가지고 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차원 리스트)
# 일단 9개를 Fasle로 표현하고, 방문할떄마다 True로 바꾸어 줄 것임.
# 노드 번호와 통일시키기 위해 graph 에도 grpah[0]에 빈 리스트를 넣어주었고, 여기서도 9개로.
visited = [False] * 9

# 정의된 DFS함수 호출
DFS(graph, 1, visited)
## 출력값 ---> 1 2 7 6 8 3 4 5

 

2. BFS

• Breadth First Search, 너비 우선 탐색
• 가까운 노드부터 탐색하는 알고리즘
• 주로 큐를 활용하여 구현됨.
  • 큐 : 선입선출 방식의 자료구조
• 동작방식
  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모든 큐에 삽입하고 방문처리를 한다.
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 진행한다.
• 동작방식을 아래 그래프를 예시로 이해해보자.

그래프 예시

• 큐에 들어간 순서는 1, 2, 3, 8, 7, 4, 5, 6 이 된다.

 

▶ BFS를 코드로 구현해보기

• 위에서 다룬 동일한 그래프를 가지고 BFS코드를 구현해 볼것이다.
• deque 라이브러리를 사용할 수 있기에 구현이 간단하다.
• deque 라이브러리를 사용하면 O(N)의 시간이 소요된다.
  • 따라서 일반적으로 재귀함수를 사용하는 DFS 보다 수행 시간이 더 효율적이다.

from collections import deque

# BFS 메서드 정의
def BSF(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리를 활용 할 것이다.
    queue = deque([start])
    # 현재 노드를 방문처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에 들어간 원소들이 순서대로 출력된다.
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입하자.
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 연결리스트 방식으로 표현
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)

## 출력될 결과 ---> 1 2 3 8 7 4 5 6