그래프 탐색 알고리즘 : DFS / BFS
탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다. 대표적인 그래프 탐색 알고리즘 으로는 DFS 와 BFS 가 있습니다. DFS / BFS 는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 합니다.
용어정리
그래프는 노드(Node) 와 간선(Edge) 으로 표현되며, 이때 노드를 정점(Vertex) 이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다 라고 표현한다.
인접 행렬 방식과 인접 리스트 방식
인접 행렬•
2 차원 배열로 그래프의 연결 관계를 표현하는 방식
•
2 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.
실제 코드에서 논리적으로 정답이 될 수 없는 큰 값 중에서 99999999999999 등의 값으로 초기화 하는 경우가 많다.
INF = 9999999 # 무한의 비용 선언
# 2 차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
Python
복사
◦
메모리 측면에서 보면 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다.
인접 리스트•
리스트로 그래프의 연결 관계를 표현하는 방식
•
역시 2 차원 배열을 사용하며, append() 와 메서드를 이용한다.
# 행(Row) 이 3 개인 2 차원 리스트로 인접 리스트 표현
graph = []
# 노드 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)
Python
복사
◦
인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다. 하지만 이와 같은 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 연결된 데이터를 하나씩 확인해야 하기 때문이다.
DFS(Depth-First Search)
DFS 는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다.
DFS 는 스택 자료구조(혹은 재귀 함수) 를 이용한다.[구체적인 동작 과정]
1.
탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2.
스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3.
더이상 2 번의 과정을 수행할 수 없을 때까지 반복한다.
파이썬의 경우 각 노드가 연결된 정보를 표현할 때 2 차원 리스트를 활용하며, 0번째 인덱스는 [] 와 같이 비워둔다.
실전문제 음료수 얼려 먹기
풀이방법1.
특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 ‘0’ 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
2.
방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
3.
1 과 2 의 과정을 반복하여 방문하지 않은 지점의 수를 센다.
BFS(Breadth-First Search)
BFS 는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS 는 큐(혹은 큐 자료구조)를 이용하며, 구체적인 동작 과정은 다음과 같다.1.
탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2.
큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3.
더이상 2 번의 과정을 수행할 수 없을 때까지 반복한다.
큐 구현을 위해 deque 라이브러리를 사용해야 한다.from collections import deque
큐 에서 원소를 뽑을때는 .popleft() 를 사용한다.