"깊이 우선 탐색(DFS)이란 그래프 탐색 알고리즘 중에서 루트 노드(또는 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 주로, 모든 노드를 방문하고자 하는 경우에 사용된다."
그래프 탐색이란?
: 하나의 정점에서 시작해서 차례대로 모든 정점에 방문하는 것
대표적인 그래프 탐색 방법으로는 너비 우선 탐색과 깊이 우선 탐색이 존재한다. 그 중 깊이 우선 탐색에 대해서 알아보고자 한다.
(1)
시작 정점과 연결된 노드를 찾아 방문한다.(2) ~ (4)
방문한 노드와 연결된 노드를 방문한다.(5)
노드 3으로 돌아와서 노드 3과 연결된 노드 중 방문하지 않은 노드가 있는지 확인한다.(2) ~ (4)
과정을 반복한다.(6) ~ (9)
위 과정을 반복하고 루트 노드로 돌아왔을 때 탐색을 종료한다.위와 같은 그래프를 구현하는 방법으로는 인접행렬과 인접 리스트 방식으로 구현할 수 있다.
인접 행렬: 2차원 배열
인접 리스트: LinkedList, ArrayList ..
인접 행렬 시간복잡도 : O(N^2)
인접 리스트 시간복잡도 : O(N+E)
N: 노드의 수
E: 간선의 수
val graph = mutableListOf<MutableList<String>>()
val result = mutableListOf<String>()
val dx = listOf(-1, 1, 0, 0)
val dy = listOf(0, 0, -1, 1)
fun main() {
repeat(5) {
graph.add(readln().split(" ").toMutableList())
}
for (i in 0 until 5) {
for (j in 0 until 5) {
dfs(i to j, graph[i][j])
}
}
println(result.count())
}
fun dfs(start: Pair<Int, Int>, s: String) {
if (s.length == 6) {
if (s !in result) {
result.add(s)
}
return
}
val x = start.first
val y = start.second
for (i in 0 until 4) {
val a = x + dx[i]
val b = y + dy[i]
if (a in 0 until 5
&& b in 0 until 5) {
dfs(a to b, s + graph[a][b])
}
}
}
재귀 호출 방식을 활용하였다.
val graph = mutableListOf<MutableList<String>>()
val result = mutableListOf<String>()
val dx = listOf(-1, 1, 0, 0)
val dy = listOf(0, 0, -1, 1)
fun main() {
repeat(5) {
graph.add(readln().split(" ").toMutableList())
}
for (i in 0 until 5) {
for (j in 0 until 5) {
dfs(i to j, graph[i][j])
}
}
println(result.count())
}
fun dfs(start: Pair<Int, Int>, ss: String) {
val stack = Stack<Triple<Int, Int, String>>()
stack.add(Triple(start.first, start.second, ss))
while (stack.isNotEmpty()) {
val (x, y, s) = stack.pop()
if (s.length == 6) {
if (s !in result) {
result.add(s)
}
continue
}
for (i in 0 until 4) {
val a = x + dx[i]
val b = y + dy[i]
if (a in 0 until 5
&& b in 0 until 5) {
stack.add(Triple(a, b, s + graph[a][b]))
}
}
}
}
stack 자료구조를 활용하였다.