완전 탐색 문제를 풀면서 완전 탐색을 구현하는 방식에는 두 가지 방법(인접 행렬과 인접 리스트)이 있다는 것을 알게 되었습니다.
각 방식이 어떤 경우에 유리하게 활용되는지 문제를 통해 정리해 두면 좋을 것 같아 이번 글을 작성하게 되었습니다.
이번 글에서는 완전 탐색을 인접 행렬과 인접 리스트를 사용하여 해결할 때의 차이점과 각각의 장단점을 두 가지 문제를 예제로 설명하겠습니다.
1. 인접 행렬을 사용하는 경우
1.1 인접 행렬(Adjacency Matrix) 개념
- 배열(Array) 기반이며, BooleanArray를 사용하여 간선 유무를 표현합니다.
- graph[i][j] = true이면 i번 노드와 j번 노드가 연결된 것입니다.
- graph[i][j] = false이면 연결되지 않은 상태입니다.
- 공간 복잡도: O(N^2) (N: 노드 개수)이며, 메모리를 많이 사용하지만 접근 속도가 빠릅니다.
- 노드 간 연결 여부를 O(1)로 확인할 수 있습니다.
1.2 예제 문제 1: 배추흰지렁이 문제 (DFS 활용)
문제 설명
배추가 상하좌우로 인접해 있을 경우 하나의 배추흰지렁이가 보호할 수 있는 배추의 그룹이 됩니다.
배추밭이 주어졌을 때, 최소 몇 마리의 배추흰지렁이가 필요한지를 구하는 문제입니다.
문제 해결 방법
- 배추밭을 2차원 배열(인접 행렬)로 표현합니다.
- DFS를 이용하여 한 덩어리(인접한 배추 그룹)를 탐색합니다.
- 탐색이 끝날 때마다 배추흰지렁이 개수를 증가시킵니다.
1.3 인접 행렬을 이용한 풀이 (DFS)
import java.io.BufferedReader
import java.io.InputStreamReader
const val MAX = 60
// 이동 방향 (상, 하, 좌, 우)
val dirR = intArrayOf(1, -1, 0, 0)
val dirC = intArrayOf(0, 0, 1, -1)
lateinit var graph: Array<BooleanArray>
lateinit var visited: Array<BooleanArray>
var answer = 0
// DFS 탐색 (연결된 배추 그룹 찾기)
fun dfs(y: Int, x: Int) {
visited[y][x] = true
for (dirIdx in 0 until 4) {
val newY = y + dirR[dirIdx]
val newX = x + dirC[dirIdx]
if (graph[newY][newX] && !visited[newY][newX]) {
dfs(newY, newX)
}
}
}
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val t = br.readLine().toInt()
repeat(t) {
val (M, N, K) = br.readLine().split(" ").map { it.toInt() }
graph = Array(MAX) { BooleanArray(MAX) { false } }
visited = Array(MAX) { BooleanArray(MAX) { false } }
repeat(K) {
val (x, y) = br.readLine().split(" ").map { it.toInt() }
graph[y + 1][x + 1] = true
}
answer = 0
for (i in 1..N) {
for (j in 1..M) {
if (graph[i][j] && !visited[i][j]) {
dfs(i, j)
answer++
}
}
}
println(answer)
}
}1.4 인접 행렬을 선택한 이유
- 배추밭을 2차원 배열로 표현하면 직관적으로 이해하기 쉽습니다.
- 배추가 있는 위치에서 상하좌우(4방향)만 탐색해야 하므로, graph[i][j]에 O(1)로 접근할 수 있습니다.
- DFS를 사용할 때 인접한 배추를 빠르게 찾을 수 있습니다.
인접 리스트를 사용하지 않은 이유
- 배추밭은 노드(배추) 간 연결보다 전체적인 공간을 표현하는 것이 중요하므로, 인접 리스트보다 2차원 배열이 더 직관적입니다.
- 상하좌우(4방향) 탐색이 필요하므로, 인접 리스트를 사용할 경우 탐색 시 매번 리스트를 순회해야 하는 비효율이 발생할 수 있습니다.
2. 인접 리스트를 사용하는 경우
2.1 인접 리스트(Adjacency List) 개념
- 리스트(List) 기반이며, mutableListOf<Int>()를 사용하여 연결된 노드들을 동적으로 저장합니다.
- 공간 복잡도: O(N + M) (N: 노드 개수, M: 간선 개수)이며, 메모리를 절약할 수 있습니다.
- 간선이 존재하는지 확인하려면 리스트를 순회해야 하므로 O(N)이 소요됩니다.
2.2 예제 문제 2: DFS & BFS 탐색 문제
문제 설명
주어진 그래프를 DFS와 BFS를 이용하여 탐색한 결과를 출력하는 문제입니다.
방문할 수 있는 노드가 여러 개이면 작은 번호부터 방문해야 합니다.
문제 해결 방법
- 그래프를 인접 리스트로 표현합니다.
- DFS로 깊이 우선 탐색을 수행합니다.
- BFS로 너비 우선 탐색을 수행합니다.
2.3 인접 리스트를 이용한 풀이 (DFS & BFS)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val (N, M, V) = br.readLine().split(" ").map { it.toInt() }
val graph = Array(N + 1) { mutableListOf<Int>() }
repeat(M) {
val (a, b) = br.readLine().split(" ").map { it.toInt() }
graph[a].add(b)
graph[b].add(a)
}
for (i in 1..N) {
graph[i].sort()
}
val visitedDFS = BooleanArray(N + 1)
dfs(V, graph, visitedDFS)
println()
val visitedBFS = BooleanArray(N + 1)
bfs(V, graph, visitedBFS)
}
// DFS 구현 (재귀)
fun dfs(node: Int, graph: Array<MutableList<Int>>, visited: BooleanArray) {
visited[node] = true
print("$node ")
for (next in graph[node]) {
if (!visited[next]) {
dfs(next, graph, visited)
}
}
}
// BFS 구현 (Queue 사용)
fun bfs(start: Int, graph: Array<MutableList<Int>>, visited: BooleanArray) {
val queue: Queue<Int> = LinkedList()
queue.add(start)
visited[start] = true
while (queue.isNotEmpty()) {
val current = queue.poll()
print("$current ")
for (next in graph[current]) {
if (!visited[next]) {
queue.add(next)
visited[next] = true
}
}
}
}2.4 인접 리스트를 선택한 이유
- 연결된 노드들만 저장하여 메모리를 절약할 수 있습니다.
- 간선이 적은 희소 그래프에서 유리합니다.
- BFS/DFS 탐색 시, 연결된 노드만 탐색하므로 효율적입니다.
결론
- 배추흰지렁이 문제 → 인접 행렬 사용 (완전 탐색이 필요하므로 2차원 배열이 직관적)
- DFS/BFS 탐색 문제 → 인접 리스트 사용 (메모리 절약 및 빠른 탐색)
문제링크:
https://www.acmicpc.net/problem/1012
https://www.acmicpc.net/problem/1260
반응형
