[알고리즘] DFS와 BFS

탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍의 측면에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있는데, 이 알고리즘들의 원리를 제대로 이해해야 코딩 테스트의 탐색 문제 유형을 풀 수 있다.

 

알고리즘을 공부하기 위해 필요한 자료구조 개념들

LIFO , Last In First Out

스택

• 한쪽만 뚫려있는 구조. 삽입과 추출이 한쪽에서만 진행
• push : 스택에 데이터를 넣는 작업
• pop : 스택에서 데이터를 꺼내는 작업 가장 윗 부분 : top, 가장 아랫부분: bottom

FIFO, First In First Out

큐

• 한쪽에서는 데이터 삽입만, 다른 한쪽에서는 데이터 추출만 진행
• enQueue : 데이터 삽입 작동 <-> deQueue : 데이터 추출 작동
• front : 머리, rear : 꼬리 데이터 삽입 -> rear 다음에 새로운 데이터 삽입(rear +1의 위치) 데이터 추출 -> 가장 먼저 들어온 데이터가 나가야 하기 때문에 머리 위치가 추출
• enQueue 큐 공간이 빈 상태 : front = rear = -1 데이터 삽입 : rear를 오른쪽으로 한 칸 이동 rear = 0
• deQueue 맨 왼쪽의 데이터를 꺼내는 것과 같음 중간 데이터를 추출하는 것은 불가. 맨 왼쪽의 데이터를 꺼낼 수 있다

자료 구조의 일종

• Node :정점
• Edge : 간선, 정점간의 관계를 나타낸다
• G = (V, E)

OverFlow

특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생하는 것으로, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다.

 

UnderFlow

특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행 시에 발생한다.

그래프

 

 

• Path : 정점 A에서 B로 가는 경로 Cycle : 정점 A에서 다시 A로 돌아오는 경로
• Simple Path and Simple Cycle : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로 사이클. 특별한 말 없으면 일반적으로 해당
• A -> C : 간선에 방향이 있다 A-C : 간선에 방향이 없다. Bidirectional Graph라고도 한다.

→ 두 정점 사이에 간선이 여러 개일수도 있다.

• 루프 : 간선 양 끝 점이 같은 경우
• 가중치 : 간선에 가중치가 있는 경우에는 A에서 B로 이동하는 거리, 이동하는 데에 필요한 시간, 이동하는 데에 필요한 비용 등등등...
• 차수 : 정점과 연결되어 있는 간선의 개수. 방향 그래프의 경우 In-Degree / Out-degree로 나누어서 차수를 계산

[그래프 저장 방법] 인접 행렬 / 인접 리스트 / 한 정점 x와 연결된 간선을 효율적으로 찾는 구조를 만들기 위해 그래프 저장 방법 2가지를 배운다.

 

Adjacency Matrix, 인접 행렬

정점의 개수를 V라고 했을 때 VxV 크기의 이차원 배열을 이용한다. A[i][j] =1 (i -> j 간선 존재 시), A[i][j] = 0 (없을 때) A[i][j] = 2 (간선 존재 및 가중치 w), A[i][j] = 0 (없을 때)

# 인접행렬(Adjacent Matrix) 구현 예시
# 무한의 값 임의 지정
INF = 999999999

graph = [[0,7,5],
        [7,0, INF],
        [5, INF, 0]]

print(graph)

 

정점 V, 간선 E일 때 공간 = V^2 한 정점에 연결된 모든 간선을 찾는 시간 복잡도 : O(V)

→ 두 노드간의 엣지에 직접 접근할 수 없다.

→ 모든 노드쌍의 관계를 표현해야 하기 때문에 공간복잡도가 O(V^2) 소요된다

따라서 인접 행렬은 밀집(엣지 수가 많은) 그래프 형태에서 좋은 성능을 발휘하고 적절한 공간을 소요한다고 여겨지나, 희소(엣지 수가 적은) 그래프 형태에서는 공간낭비가 심해 메모리 초과가 발생할 여지가 있다.

 

Adjacency List , 인접 리스트

# 인접 리스트 구현 예시
graph = [[] for _ in range(3)]

graph[0].append((1,7))
graph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

리스트를 이용해서 구현 -> 간선이 몇 개가 있을 지 알 수 없는 경우에 사용하며, 동적으로 하나씩 증가시켜 사용한다

A[i] = i와 연결된 정점을 리스트로 포함 가중치 존재 시 해당 정점 번호와 가중치를 묶어서 저장

→ 두 노드 간 엣지 존재 여부를 조사하기 위해서는 순차 탐색을 해야함 → O(V) 시간 소요

→ 인접 행렬과 달리 존재하는 엣지만을 표현하기 때문에 O(E) 만큼의 공간 소요

따라서 모든 엣지 또는 적은 엣지를 조사해야 하는 그래프 알고리즘에서 유용하게 활용

그러나 밀집 그래프 형태의 문제에서는 1번 특징으로 인해 시간 초과 문제 발생의 여지가 있다.

• Edge List, 간선 리스트 엣지를 중심으로 표현하는 방법 [노드1(혹은 출발 노드), 노드2(혹은 도착 노드), 가중치] 형태의 자료구조를 리스트 또는 배열 형태로 저장 -> 모든 엣지를 살펴보는 알고리즘에서 간편하고 직관적으로 활용이 가능하다.

인접 행렬 방식과 인접 리스트 방식의 차이

메모리 측면

인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 인접 리스트 방식은 연결된 데이터를 하나씩 연결해야 하므로, 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.

 

Ex. 노드 1과 노드 7이 연결되어 있는 지 확인해야 할때, 인접 행렬 방식에서는 graph[1][7] 만 확인하면 되지만, 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서부터 차례대로 확인해야 한다. 그렇기에 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다.

DFS : 깊이 우선 탐색

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

DFS는 스택 자료구조(or 재귀함수) 이용

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

• 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 -> BFS보다 좀 더 간단함 -> 검색 속도 자체는 BFS 비해 느림

BFS : 너비 우선 탐색

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

BFS는 큐 자료구조를 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에는 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복

: 시작 노드부터 가까운 노드를 우선적으로 탐색하는 것을 알 수 있다.

https://blog.kakaocdn.net/dn/cQYkI8/btqB8oDsMGe/EEYm0cKGYhxTR0kJhGiJPK/img.gif

[DFS와 BFS 활용한 문제 유형/응용]

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제

: 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다. 둘 중 편한 것을 사용하자

1. 경로의 특징을 저장해둬야 하는 문제

: 예로 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안되거나, 각각의 경로마다 특징을 저장해두어야 할 때, DFS를 사용한다.

1. 최단거리 구해야 하는 문제

: 미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다.

• 검색 대상 그래프가 정말 크다면 DFS 고려
• 검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS