[알고리즘] 깊이우선탐색(DFS) & 너비우선탐색(BFS)

https://rvrlo.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84Graph

[자료구조] 그래프(Graph)

그래프 탐색을 알기 위해 그래프에 대한 기본 지식이 있어야 한다.

 

그래프 탐색의 가장 대표적인 DFS와 BFS

 

---

 

깊이 우선 탐색
Depth First Search : DFS

 

현재 정점과 인접한 간선들을 하나씩 검사하다가 아직 방문하지 않은 정점으로 향하는 간선이 있으면 그 간선을 따라간다. 그래프 아래로 깊숙히 들어가 더 이상 갈 곳이 없으면 마지막에 왔던 간선을 따라 다시 뒤로 돌아간다. 스택의 모양을 생각하면 이해하기 편하다. 

간선을 따라 하나씩 내려가면서 스택에 정점을 넣는다. 더 이상 갈 곳이 없으면 마지막에 저장한 정점으로 다시 이동한다. 선입선출의 스택과 같은 모양을 하고 있어, DFS를 할 때 스택을 사용한다.

 

• DFS를 하기 위해 시작 노드와 연결된 노드를 나타낼 변수 두개가 필요하다.
  시작 노드를 v, 연결된 노드를 w 라고 한다면
  
  정점 v에서 w정점을 방문하면 스택에 v를 push한다. 정점 w로 이동했으니 지금 위치해 있는 곳은 w이다. 현재 위치를 나타내는 변수를 v로 사용하고 있으니 v=w 를 통해 현재 위치를 대입하여 반복한다.
  
  
• 위 처럼 반복하다 인접 노드(간선으로 연결된 노드)가 없으면 pop을 진행하여 가장 마지막으로 push한 노드를 꺼내온다. 마지막 노드를 다시 v에 대입한다.

스택이 비워질 때까지 위의 과정을 반복하다보면 모든 노드에 대한 탐색이 끝나있다.

 

---

 

너비 우선 탐색
Breadth First Search : BFS

 

인접한 노드로 계속 내려가는 DFS와 달리, BFS는 현재 노드에서 가장 가까운 노드를 우선 탐색한다. 만약 노드 A와 인접한 노드가 B, C가 있고, B와 인접한 노드 D가 있을 경우 아래의 형태를 띄게 된다.

위는 사이클이 돌지 않는 무향 그래프이다. 만약 A에서 탐색을 시작한다고 할 때, DFS와 BFS 모두 모든 노드를 방문할 수 있지만, 그 순서가 다르다. 위 그래프로 DFS와 BFS를 비교하면서 설명하겠다.

 

 

순서를 기준으로 하는 DFS의 경우는 아래와 같다.

파란색 선대로 간선으로 연결된 노드를 우선 탐색한다. A와 인접한 노드 B를 탐색하고, B와 인접한 노드 D를 탐색한다. 그럼 스택에는 A-B-D 순서대로 쌓이게 된다. D에서 더 이상 진입할 노드가 없으니 마지막 노드 B로 이동하고, B에서 다시 A로 이동하게 된다. A와 인접한 노드 중 탐색하지 않은 C를 다시 탐색한다. 스택에는 B와 D가 빠지고, C가 push되어 A - C가 남아있게 된다. 인접 노드가 없으니 C와 A 모두 pop을 하면 스택은 비워지면서 모든 노드가 탐색 완료 된다.

더 깊숙히 들어간다고 하여 깊이 우선 탐색이라고 하는 방법이다.

 

너비 우선 탐색의 그림은 아래와 같다.

거리를 기준으로 하는 너비 우선 탐색은 A를 기준으로 인접한 노드를 모두 방문한다. BFS의 경우 큐를 사용해 설명할 수 있다. A를 큐에 넣고, 인접한 노드 B와 C를 방문하여 enQueue한다. 큐에는 A - B - C 가 들어간 상태이다. A와 인접한 노드가 없으면 deQueue를 진행하여 큐에 들어간 노드를 빼낸다. 먼저 들어간 것이 먼저 나와 A가 빠지게 되면서 큐에는 B - C 가 남게 된다. B를 기준으로 다시 인접한 노드를 방문한다. 위 내용을 반복하여 큐가 모두 비게 되면 탐색이 끝난 것이다.

인접한 노드를 기준으로 더 넓게 펼쳐진다 하여 너비 우선 탐색이라고 한다.

 

너비 우선 탐색은 다익스트라의 최단거리 알고리즘, 프림의 최소 스패닝 트리 알고리즘 등에서 유용하게 사용 된다.

 

 

---

 

 

백준 1260번 문제가 DFS와 BFS 모두를 경험해볼 수 있다.

 

 

 

문제

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

 

입력

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

 

출력

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

 

---

 

위 내용을 파이썬을 이용해서 풀어보았다.

 

from collections import deque
import sys

 

파이썬에는 deque라는 패키지가 있어 큐나 스택을 사용할 때 유용하게 사용 가능하다.

 

 

# 깊이 우선 탐색
def DFS(Graph, start):
    visited[start] = True
    print(start, end=' ')

    for i in Graph[start]:
        if not visited[i]:
            DFS(Graph, i)

 

먼저 DFS를 계산할 함수를 정의하였다.

visitied를 이용해 방문한 노드인지 아닌지 알아낼 수 있다. 그래프의 시작 노드부터 만약 방문하지 않은 노드라면, 재귀를 통해 다음 노드로 계속 이동하여 탐색한다. 재귀는 스택의 모양을 표현할 가장 간단한 호출 형태로 스택도 재귀를 통해 간단하게 표현할 수 있어 재귀로 사용하였다.

 

 

# 너비 우선 탐색
def BFS(Graph, start):
    visited[start] = True
    que = deque([start])

    while que:
        u = que.popleft()
        print(u, end=' ')

        for i in Graph[u]:
            if not visited[i]:
                visited[i] = True
                que.append(i)

 

다음은 BFS를 계산할 함수이다.

u는 방문한 노드 → 출력을 진행할 노드를 의미한다. 방문한 노드를 큐에 삽입하고, 계속 꺼내오면서 다음 노드로 탐색을 진행한다. 선입선출을 위한 popleft() 함수를 사용할 수 있도록 deque로 선언하여 사용해야 한다.

 

 

메인 코드는 아래와 같다.

N, M, V = map(int, sys.stdin.readline().split())

# 1.
graph = [ [] for x in range(N+1) ]
visited = [False] * (N+1)

# 2.
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a] += [b]
    graph[b] += [a]

# 3.
for i in graph:
    i = i.sort()

# 4.
DFS(graph,V)
print()

visited = [False] * (N+1)
BFS(graph,V)

 

# 1.
문제에 맞는 입력 형태로 값을 입력받는다. 노드 방문 유무를 나타내기 위한 visited 리스틀 각 노드의 개수만큼 생성한다. N개의 정점을 입력받아 그래프와 방문 모두 N+1개로 생성하는 이유는 각 인덱스 번호를 노드의 번호로 사용하기 위함이다. 출력 시에 좀 더 편한 연산을 위해 (N+1)로 지정하였다.

 

# 2.
연결된 간선을 입력받는다. 각 인덱스에 들어간 요소는 노드에 연결된 다른 노드를 의미한다. 1번 노드와 연결된 노드가 2랑 3일 경우, 1번 인덱스의 요소값은 [2, 3] 이다. 무향 그래프로 서로 양방향 연결을 진행한다.

 

# 3.
정점의 번호가 작은 것을 먼저 방문하기 위해 각 인덱스의 요소를 오름차순으로 정렬하였다.

 

# 4.
DFS 연산이 끝난 후 visited의 요소값이 바뀌었기 때문에 BFS 연산 진행 전 방문값을 False로 되돌려 준다.