깊이 우선 탐색(DFS)

깊이 우선 방식으로 정점을 방문하여 그래프를 탐색하는 그래프 탐색 알고리즘이다. 방문한 각 노드의 부모 노드를 추적하여 소스 노드와 그래프의 다른 노드 사이의 경로를 구성한다.

🚀 알고리즘 논리

DFS는 스택을 사용하여 방문한 노드를 추적한다. 소스 노드에서 시작하여 각 이웃 노드를 탐색하는 방식으로 작동한다.

🏁 알고리즘 동작 과정

1. 시작점을 스택에 추가
2. 스택이 비어있지 않다면, 스택에서 정점을 빼서 이웃 정점을 방문
3. 이웃을 방문한 적이 없는 경우, 방문한 것으로 표시하고 스택에 추가한 후 2단계를 반복
4. 이웃을 방문한 경우, 건너뛰고 2단계를 계속 진행
5. 모든 정점을 방문했다는 것을 나타내는 스택이 비워질 때까지 2~4단계를 반복 (재귀적)

⏲ 시간 복잡도

O(V+E) (V: 노드의 수, E: 그래프의 가장자리 수)

👍 장점 & 👎 단점

장점

• 단순하고 구현이 쉽다. 방문한 노드를 추적하고 그래프를 가로 지르는 데 단순한 재귀 함수만 있으면 된다.

단점

• 사이클이 많거나 연결이 끊어진 경우, 다른 알고리즘이 더 효율적일 수 있다.
• DFS가 사이클을 만나 무한 루프에 갇힐 수 있다.

📚 예제: N-Queen 문제

let n = Int(readLine()!)!

func checkQueen(_ arr: [Int], _ index: Int) -> Bool {
    for i in 0..<index {
    if arr[i] == arr[index] || abs(arr[i] - arr[index]) == abs(i - index) {
        return false
        }
    }
    return true
}

func nQueen(_ arr: inout [Int], _ cnt: Int, _ answer: inout Int) {
    if cnt == arr.count {
        answer += 1
        return
    }

    for i in 0..<arr.count { // 가능한 모든 열을 검사
        arr[cnt] = i
        if checkQueen(arr, cnt) {
            nQueen(&arr, cnt + 1, &answer)
        }
    }
}

func solution(_ n: Int) -> Int {
    var answer = 0 // 정답 카운트
    var data = Array(repeating: 0, count: n)
    nQueen(&data, 0, &answer)
    return answer
}
print(solution(n))