그래프(Graph)란 무엇일까?
그래프는 정점(Vertex)와 간선(Edge)으로 구성된 자료구조이다.
- 정점(Vertex) : 그래프의 구성요소로, 사람이나 도시처럼 개별 요소를 나타낸다.
- 간선(Edge) : 정점들을 연결하는 선이다. 두 정점 사이의 관계(예:도로, 친구 관계)를 나타낸다.
- 예시 : 학교에서 여러 학생(정점)들이 친구 관계(관선)를 맺고 있는 것을 그래프로 생각할 수 있다.
그래프의 표현 방법
그래프를 컴퓨터에서 표현하는 방법에는 여러 가지가 있다. 가장 일반적인 두 가지 방법은 인접 리스트와 인접 행렬이다.
- 인접 리스트(Adjacency List) : 각 정점에 연결된 정접들의 리스트를 저장한다.
예시
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]
- 인접 행렬(Adjacency Matrix) : 정점 간의 연결 여부를 2차원 배열 형태로 저장한다.
예시
matrix[0][1] = 1
현실 세계에서의 그래프 예시로는
- 학교 네트워크 : 학생들을 정점으로 하고, 친구 관계를 간선으로 표현
- 지도와 도로 : 도시를 정점, 도로를 간선으로 표현하여 경로 탐색 문제 해결
- 인터넷 : 웹 페이지를 정점으로 하고, 하이퍼링크를 간선으로 표현하여 검색 알고리즘 등에 응용
등이 있다.
깊이 우선 탐색(DFS, Depth First Search)
1. DFS 의 기본 원리
DFS는 시작 정점에서 출발하여 한 방향으로 끝까지 탐색한 후, 더 이상 진행할 수 없으면 마지막 분기점으로 돌아가 다른 경로를 탐색하는 방식이다. 이러한 과정은 재귀 호출을 통해 자연스럽게 구현된다.
2. DFS의 동작 방식과 재귀 호출
동작 방식 :
- 시작 정점을 방문하고, 방문 목록에 추가한다.
- 현재 정점에서 인접한 정점 중 아직 방문하지 않은 정점을 선택한다.
- 선택한 정점으로 이동하여 같은 과정을 반복한다.
- 더 이상 방문할 정점이 없으면, 이전 정점으로 되돌아가 (Backtracking) 다른 경로를 탐색한다.
재귀 호출 : DFS는 재귀적으로 자신을 호출하면서, 깊은 경로를 먼저 탐색한다.
3. DFS의 장단점
장점 :
- 구현이 간단하고 직관적이다.
- 경로 탐색, 사이클 검출 등 다양한 문제에 응용할 수 있다.
단점 :
- 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.
- 최악의 경우 모든 정점을 방문하므로, 시간 복잡도가 높을 수 있다.
4. DFS 구현 예제(Kotlin)
// DFS를 구현하기 위해, 방문한 정점을 기록할 집합과 재귀 함수를 사용합니다.
fun dfs(node: Int, visited: MutableSet<Int>, graph: Map<Int, List<Int>>) {
// 현재 정점을 방문 목록에 추가하고, 출력합니다.
visited.add(node)
println("DFS 방문: $node")
// 현재 정점과 연결된 모든 정점을 순회합니다.
for (neighbor in graph[node] ?: emptyList()) {
// 아직 방문하지 않은 정점이면 재귀 호출합니다.
if (!visited.contains(neighbor)) {
dfs(neighbor, visited, graph)
}
}
}
fun mainDFS() {
// 간단한 무방향 그래프를 인접 리스트로 표현합니다.
val graph: Map<Int, List<Int>> = mapOf(
0 to listOf(1, 2), // 0번 정점은 1번,2번 정점에 간선을 갖는다.
1 to listOf(0, 3),
2 to listOf(0, 3),
3 to listOf(1, 2)
)
val visited = mutableSetOf<Int>()
println("=== DFS 탐색 결과 ===")
dfs(0, visited, graph)
}
위에 코드에서 인접 리스트로 표현된 그래프를 실제로 살펴보면
위 그림에서 방향성을 나타내는 화살표를 빼고 안쪽에 있는 간선 3개를 빼면 위의 코드의 그래프이다.
해당 코드를 실행해보면 시작 정점 0에서 시작하여 0 > 1 > 3> 2 순으로 방문을 진행하고, 각 단계에서 재귀 호출이 이루어지고, 되돌아가며 다른 경로를 탐색하는 모습은 미로에서 한 길로 쭉 들어갔따가 다시 돌아가는 것과 비슷하다.
너비 우선 탐색(BFS, Breadth First Search)
1. BFS의 기본 원리
BFS는 시작 정점에서부터 인접한 모든 정점을 먼저 방문하고, 그 다음 단계의 정점을 방문하는 방식이다. 즉, "가까운 것부터 넓게" 탐색하는 방법이다.
2. BFS의 동작 방식과 큐의 역할
동작 방식 :
- 시작 정점을 방문하고, 큐에 추가한다.
- 큐에서 정점을 꺼내 그 정점과 인접한 모든 정점을 방문한다.
- 방문한 정점을 큐에 추가하면서, 순차적으로 탐색한다.
큐의 역할 : BFS에서는 먼저 들어온 정점을 먼저 처리하는 FIFO(선입선출) 자료구조인 큐를 사용한다.
3. BFS의 장단점
장점 :
- 최단 경로를 찾는 데 효과적이다.
- 큐를 사용하므로 DFS보다 스택 오버플로우 위험이 적다.
단점 :
- 모든 인접 정점을 저장해야 하므로 메모리 사용량이 많아질 수 있다.
- 그래프의 모든 정점을 한 번씩 방문하므로, 큰 그래프에서는 시간이 오래 걸릴 수 있다.
4. BFS 구현 예제(Kotlin)
import java.util.LinkedList
import java.util.Queue
fun bfs(start: Int, graph: Map<Int, List<Int>>) {
val visited = mutableSetOf<Int>()
val queue: Queue<Int> = LinkedList()
// 시작 정점을 방문 처리하고 큐에 추가합니다.
visited.add(start)
queue.offer(start)
while (queue.isNotEmpty()) {
val node = queue.poll()
println("BFS 방문: $node")
// 현재 정점과 연결된 모든 정점을 순회하며 방문하지 않은 정점을 큐에 추가합니다.
for (neighbor in graph[node] ?: emptyList()) {
if (!visited.contains(neighbor)) {
visited.add(neighbor)
queue.offer(neighbor)
}
}
}
}
fun mainBFS() {
// 간단한 무방향 그래프를 인접 리스트로 표현합니다.
val graph: Map<Int, List<Int>> = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3),
2 to listOf(0, 3),
3 to listOf(1, 2)
)
println("=== BFS 탐색 결과 ===")
bfs(0, graph)
}
코드의 실행에 대해서 생각해보면 시작 정점 0에서 시작하여, 먼저 0에 인접한 1과 2를 방문하고, 그 후 1과 2의 인접 정점(3 등)을 방문하는 순서로 진행된다.
DFS와 BFS의 비교
1. 탐색 방식의 차이
- DFS : 한 방향으로 깊게 들어간 후, 더 이상 진행할 수 없으면 되돌아가는 방식 -> "깊이 우선"으로 탐색한다.
- BFS : 시작 정점에서 가까운 정점을 모두 방문한 후, 그 다음 레벨로 넘어가는 방식 -> "너비 우선"으로 탐색한다.
2. 시간 복잡도와 메모리 사용 비교
- 시간 복잡도 : 두 알고리즘 모두 그래프의 정점 수(V)와 간선 수 (E)에 따라 O(V+E)의 시간 복잡도를 가진다.
- 메모리 사용 : DFS는 재귀 호출(또는 스택)을 사용하므로 깊이에 따라 메모리 사용량이 결정된다. / BFS는 큐에 모든 인접 정점을 저장하므로, 그래프가 넓을 경우 메모리 사용량이 증가할 수 있다.
언제 각각 사용해야 할까?
- DFS 사용 경우 : 경로 깊이가 중요한 경우 / 모든 경로를 탐색해야 하는 문제(예: 순열, 조합, 백트래킹 문제)
- BFS 사용 경우 : 최단 경로 문제 / 너비 우선 탐색을 통해 빠르게 탐색할 수 있는 경우
위의 DFS와 BFS는 문제를 더 풀어보면서 Kotlin 을 연습해봐야겠다.
'자료구조&알고리즘 > Kotlin 활용' 카테고리의 다른 글
| 프로그래머스 (기초) - 5명씩 (0) | 2025.04.18 |
|---|---|
| Kotlin 연습하기(10) - 그리디 알고리즘 (2) | 2025.04.14 |
| Kotlin 연습하기(7) - 동적 계획(DP) (0) | 2025.04.07 |
| Kotlin 연습하기(6) - 선형/이진 검색 (0) | 2025.04.04 |
| Kotlin 연습하기(5) - 버블정렬 (0) | 2025.04.02 |
