[그래프 탐색] 깊이 우선 탐색 알고리즘이란 (DFS, Depth First Search) | 백준 1260번

 

📚 배경지식

---

스택 

✔ 깊이 우선 탐색의 자료구조로 이용된다. 

 

선입후출 자료구조 (FILO, First In Last Out)

# 파이썬

stack = [] # 리스트 사용

stack.append(5) # [5]
stack.append(7) # [5, 7]
stack.append(4) # [5, 7, 4]

stack.pop()     # [5, 7] - 뒤부터 삭제
stack.pop()     # [5]

stack.append(3) # [5, 3]
stack.append(1) # [5, 3, 1]

print(stack) 		# 앞에서부터 출력: [5, 3, 1]
print(stack[::-1]) 	# 뒤에서부터 출력: [1, 3, 5]

 

큐

✔ 너비 우선 탐색의 자료구조로 이용된다. 

 

선입선출 자료구조 (FIFO, First In First Out)

# 파이썬

from collections import deque

queue = deque()

queue.append(5) # [5]
queue.append(7) # [5, 7]
queue.append(4) # [5, 7, 4]

queue.popleft() # [7, 4] - 앞에서부터 삭제
queue.popleft() # [4]

queue.append(3) # [4, 3]
queue.append(1) # [4, 3, 1]

print(queue)    # 앞에서부터 출력: deque([4, 3, 1])
queue.reverse()
print(queue) 	# 뒤에서부터 출력: deque([1, 3, 4])

 

재귀함수

✔ 그래프 탐색을 재귀함수로 구현한다.  

 

• 대표적인 예제: 팩토리얼, 최대공약수(유클리드 호제법) 구현
• 반복문으로 동일한 기능 구현이 가능하다. 반복문과 재귀함수 중 상황에 따라 효율적인 방법을 선택해서 사용.
• 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
  → 스택 프레임을 사용해야할 때 구현상 스택 라이브러리 대신 재귀함수를 이용하는 경우가 많다. 

 

깊이 우선 탐색 알고리즘

---

❔ 깊이 우선 탐색 알고리즘이란? 

그래프를 탐색하기 위한 알고리즘 중 하나이다. 

     - 여기서 탐색이란 원하는 데이터를 찾는 것!

 

깊이 우선 탐색은 원하는 데이터를 찾기 위해서 깊은 부분을 우선적으로 탐색하는 방법이다.

 

미로에서 출구를 찾는 상황을 상상해보면 이해하기 쉽다.

미로 속에서 출구를 찾을 때 한 지점에서 갈 수 있는 만큼 최대한 깊숙이 가서 길을 확인하고 만약 길이 막혀 있으면 이전 분기점으로 돌아와 다시 다른 방향으로 깊숙이 들어가서 확인한다.

깊이 우선 탐색도 마찬가지로, 한 분기점에서 최대한 깊숙이 들어가서 노드들을 확인한 뒤 다시 돌아가 다른 루트로 탐색한다. 

 

💡 구현

• 재귀호출 또는 스택 배열을 이용해 구현한다.
• 스택을 이용한 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 

 

📍 코드

백준 1260번 문제를 풀면서 DFS 코드를 작성해보자!

1260번: DFS와 BFS

 

방법 1. 재귀 함수로 구현

import sys
input = sys.stdin.readline

def DFS(graph, v, visit):
    # v번 노드에 방문 처리를 한다.
    visit[v] = True
    print(v, end=' ')
    
    # 인접한 노드를 방문한다
    for i in graph[v]:
        if not visit[i]: # 방문한 적이 없으면 방문
            DFS(graph, i, visit)
            
    
# 입력
N, M, V = map(int, input().split()) # N: 노드 개수, M: 간선 개수, V: 탐색 시작 노드 번호

# graph: 그래프 정보를 담고 있는 2차원 배열 
graph = [[] for i in range(N+1)] # graph[i]: i번 노드에 인접한 노드들의 번호가 저장된 1차원 배열

for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
for i in range(N+1):
    graph[i].sort() # 번호가 작은 노드부터 방문하기 위해 인접한 노드들을 오름차순 정렬해준다. 

# visit: 노드들의 방문 여부가 저장된 1차원 배열
visit = [False] * (N+1) # 방문된 적이 있으면 True


# 탐색 시작
DFS(graph, V, visit)

 

 

방법 2. 스택 사용

예제 1을 통해 스택을 이용한 노드 방문 과정을 그림으로 먼저 알아보자

# 1260번 예제 1

# 입력
4 5 1
1 2
1 3
1 4
2 4
3 4

# 출력
1 2 4 3
1 2 3 4

 

위 입력에 대한 graph는 다음과 같다. 

graph = [
	[],
	[2, 3, 4],	# 1번 노드와 인접한 노드 번호
	[1, 4],		# 2번 노드와 인접한 노드 번호
	[1, 4],		# 3번 노드와 인접한 노드 번호
	[1, 2, 3],	# 4번 노드와 인접한 노드 번호
]

 

 

 

깊이 우선 탐색 (DFS) vs. 너비 우선 탐색 (BFS)

---

너비 우선 탐색이란?

먼저, 너비 우선 탐색(BFS, Breadth First Search)에 대해서 간단히 알아보자.

 

BFS는 그래프 탐색 알고리즘으로, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 

 

재귀 호출 또는 큐를 이용하여 구현할 수 있다. (DFS와 달리 자료구조로 스택이 아닌 큐를 이용한다.)

 

큐를 이용한 동작 과정은 다음과 같다. 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다. 

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. (DFS는 인접한 노드 중 하나만 스택에 삽입한다.)

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. 

 

 

위의 백준 1260번 문제에서 아래와 같이 BFS와 관련된 코드를 작성해볼 수 있다.

* 재귀 호출 x (반복문 사용), 큐를 사용한 방법

import sys
input = sys.stdin.readline
from collections import deque

def BFS(graph, v, visit):
    # 반복문 시작 전 
    queue = deque([v]) # 큐 자료구조 사용
    visit[v] = True
    
    while queue: # 더 이상 방문할 노드가 없을 때까지 반복
        # 큐의 맨 앞 요소부터 방문한다
        v = queue.popleft() 
        print(v, end=' ')
        
        # 인접한 노드 중 방문 가능한 노드들을 모두 큐에 넣는다
        for i in graph[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True
    
# 입력
N, M, V = map(int, input().split()) # N: 노드 개수, M: 간선 개수, V: 탐색 시작 노드 번호

# graph: 그래프 정보를 담고 있는 2차원 배열 
graph = [[] for i in range(N+1)] # graph[i]: i번 노드에 인접한 노드들의 번호가 저장된 1차원 배열

for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
for i in range(N+1):
    graph[i].sort() # 번호가 작은 노드부터 방문하기 위해 인접한 노드들을 오름차순 정렬해준다. 

# visit: 노드들의 방문 여부가 저장된 1차원 배열
visit = [False] * (N+1) # 방문된 적이 있으면 True

# 탐색 시작
BFS(graph, V, visit)

 

BFS와 비교한 DFS의 특징

• BFS보다 느리다.
• 검색보다 순회에 더 적합하다.
• 리프 노드에만 데이터를 저장하는 정렬트리구조에서 항상 순서대로 데이터를 방문한다는 장점이 있다.
• 공통 상위를 가진 아래 리프 노드들을 한방에 잘라내는게 가능하므로, 백트래킹에 이용된다. 

 

 

 

참고한 자료 🙇‍♀️

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