[Algorithm/Swift] 깊이 우선 탐색 (DFS)

 

📚

 

벌써 6월입니다 🫠

오늘은 알고리즘에서 꼭 알아야 하는 DFS !!

저번 글에서 아주 짧게 언급했었는데

오늘은 개념 + 코드로 잘근잘근 씹어봅시다 😬

 

 

---

 

 

깊이 우선 탐색 (DFS, Depth-First Search)

그래프 탐색 알고리즘 중 하나로, 주어진 그래프에서 한 정점을 시작으로 그래프를 탐색하는 방법이다. 그래프는 정점(노드)과 간선의 집합으로 이루어진 자료구조로, 각 정점은 다른 정점과 연결될 수 있다. 탐색하려는 노드의 자식 노드부터 우선 탐색(깊이를 우선하여 탐색)하는 방식이다. 탐색 과정에서 선택한 노드에 연결된 노드들을 모두 방문한 후에는 이전 노드(부모 노드)로 돌아가서 다른 연결된 노드를 선택한다. 이 과정을 반복하여 그래프의 모든 정점을 방문한다. DFS는 주로 그래프 순회나 스도쿠 등의 문제에서 활용된다.

ko.wikipedia.org - Mre

🔎 숫자가 탐색 순서임 ! 탐색 노드의 자식 노드들을 모두 탐색하고, 다시 돌아가 탐색 노드의 다른 인접 노드 자식들을 모두 탐색.

 

 

 

DFS 구현 방법

☝🏻 재귀 함수 사용

• DFS 함수 정의
• 현재 노드를 방문한 것으로 표시
• 현재 노드와 연결된 모든 이웃 노드를 확인
• 이웃 노드 중 방문하지 않은 노드를 재귀적으로 호출하여 DFS 수행
• 재귀 호출을 통해 DFS를 진행하면서 스택의 역할을 대신

✌🏻 스택 사용

• 스택 생성 후 시작 노드를 스택에 넣기
• 스택이 빌 때까지 다음 작업 반복
  • 스택에서 노드를 하나 꺼내고 방문한 것으로 표시
  • 해당 노드와 연결된 모든 이웃 노드 중 방문하지 않은 노드를 스택에 넣기
• 모든 노드를 방문할 때까지 반복

✔️ 재귀 함수를 사용하면 코드가 간결해지지만, 호출 스택의 깊이에 따라 스택 오버플로우가 발생할 수 있다. 스택을 직접 구현하여 사용하면 호출 스택의 제한을 피할 수 있지만 코드는 좀 더 복잡해질 수 있음.

 

 

🤔 DFS에서 스택을 사용하는 이유

DFS는 깊이를 우선으로 그래프를 탐색하기 때문에 현재 노드에서 한 방향으로 최대한 깊게 탐색한 후에 다음 분기로 진행하기 위해서 스택을 활용한다. 스택은 LIFO의 특성을 가지고 있기 때문에 요소들을 역순으로 저장할 수 있다.

즉, 스택을 사용하면 현재 탐색 중인 경로를 기억하고 유지할 수 있다. 현재 노드와 연결된 이웃 노드들 중 하나를 선택하여 탐색을 진행한 후에, 다음에 탐색할 이웃 노드가 스택의 맨 위에 위치하게 된다. 이렇게 현재 경로의 끝에서부터 탐색을 계속할 수 있다.

 

 

 

Swift로 DFS 구현하기 (feat. BOJ 1260)

Baekjoon에서 예시 문제를 가져왔다. 이 문제에 기초하여 코드를 짜보겠슴 !!! DFS만 짤 것입니닷 😋 ( BFS는 다음 글에서 ∙∙∙ )

1260번: DFS와 BFS

 

📍 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

📍 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

📍 출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

📍 예제 입력

4 5 1
1 2
1 3
1 4
2 4
3 4

위 예제 입력을 기반으로 그래프를 예상해보면, 1은 2, 3, 4와 연결, 2는 1, 4와 연결, 3은 1, 4와 연결, 4는 1, 2, 3과 연결되어 있다.

 

📍 예제 출력

1 2 4 3 // DFS
1 2 3 4 // BFS

 

📍 정답

let nmr = readLine()!.split(separator: " ").map{Int($0)!}
let n = nmr[0], m = nmr[1], r = nmr[2]
var visitedDFS = [Bool](repeating: false, count: n + 1)
var answerDFS = [Int]()
var graph = [[Int]](repeating: [], count: n + 1)

for _ in 0..<m { // 정점 정보 저장
    let uv = readLine()!.split(separator: " ").map{Int($0)!}
    graph[uv[0]].append(uv[1])
    graph[uv[1]].append(uv[0])
}

dfs(r)
print(answerDFS.map{String($0)}.joined(separator: " "))

func dfs(_ start: Int) { // 재귀를 이용하여 DFS
    visitedDFS[start] = true // 현재 탐색 정점에 방문
    answerDFS.append(start) // 탐색 과정 기록 배열에 저장
    for node in graph[start].sorted() { // 인접 정점이 여러 개면 작은 것부터
        if !visitedDFS[node] { dfs(node) } // 방문하지 않은 정점일 경우 DFS
    }
}

 

📍 풀이

• visitedDFS는 방문한 정점과 방문하지 않은 정점을 구분하기 위한 배열이다.
• answerDFS는 탐색 과정을 기록하기 위한 배열이다.
• graph는 각 정점들이 간선들을 통해 다른 정점들과 연결된 정보를 저장하기 위한 배열이다.
  • 0인 정점이 없으므로 크기는 n + 1로 해준다.

// graph
[[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]

 

재귀 함수 실행 과정이 이해가 잘 안 될 수 있으니 아주 한 줄 한 줄 뜯어보자구여 🦷

1. 처음에 dfs(1)로 인해 graph[1] (1과 인접한 모든 정점)를 탐색
2. 정점 1을 방문한 것으로 표시하고 answerDFS에 정점 1을 추가
   • visitedDFS: [false, true, false, false, false]
   • answerDFS: [1]
3. 인접 정점을 순회하기 전에 graph[1]을 정렬. 정렬된 인접 정점은 [2, 3, 4]가 된다.
4. 인접 정점을 하나씩 순회하면서 재귀적으로 dfs 함수를 호출
   • 첫 번째 인접 정점인 2를 방문하지 않았으므로 dfs(2)를 호출
     • 정점 2를 방문한 것으로 표시하고 answerDFS에 정점 2 추가
       • visitedDFS: [false, true, true, false, false]
       • answerDFS: [1, 2]
     • 인접 정점을 순회하기 전에 graph[2]을 정렬. 정렬된 인접 정점은 [1, 4]가 된다.
     • 인접 정점 중에서 방문하지 않은 정점 4를 발견하고 dfs(4)를 호출
       
       • 정점 4를 방문한 것으로 표시하고 answerDFS에 정점 4를 추가
         • visitedDFS: [false, true, true, false, true]
         • answerDFS: [1, 2, 4]
       • 인접 정점을 순회하기 전에 graph[4]을 정렬. 정렬된 인접 정점은 [1, 2, 3]가 된다.
       • 1, 2는 방문한 적이 있음. 방문하지 않은 정점 3 발견하고 dfs(3) 호출
         • 정점 3을 방문한 것을 표시하고 answerDFS에 정점 3 추가
           • visitedDFS: [false, true, true, true, true]
           • answerDFS: [1, 2, 4, 3]
         • 인접 정점을 순회하기 전에 graph[3]을 정렬. 정렬된 인접 정점은 [1, 4]
         • 방문하지 않은 정점이 없음. 함수 재귀 실행 X ( 이제 빠져나가자 ~~~ 😇 )
       • dfs(3) 종료
     • 방문하지 않은 정점이 없으므로 dfs(4) 종료
   • 방문하지 않은 정점이 없으므로 dfs(2) 종료
5. 방문하지 않은 정점이 없으므로 dfs(1) 종료

 

이렇게 실행 과정을 아주 상세하게 들여다 보았다... 🥵

실행 과정을 보면, 재귀 함수를 통해 인접 정점의 자식 노드를 탐색하면서 최대한 깊게 들어갔다가 나오는 것을 확인 할 수 있다.

 

💡 재귀가 아니라 그냥 스택으로 구현하게 되면 visitedDFS(방문한 정점 배열)과 needVisitDFS(탐색해야 하는 정점 배열)을 사용한다. needVisitDFS가 비게 되면 탐색이 종료된다. 원리는 재귀와 동일하다. 코드만 조금 다를 뿐 ㅎㅎ

 

일반적으로 재귀 방식을 많이 사용하기에 저도 재귀 코드로 짜보았습니다람쥐 🐿️

 

 

 

---

 

 

재귀 코드 이렇게 하나하나 뜯어서 기록한 건 처음...

다들 이 글 보고 쉽게 이해 할 수 있길 바라며 🧠