dfs

그래프 완전 탐색 알고리즘으로 주로 재귀함수를 통해서 구현합니다.

이 문제의 입력을 받아서 구현하는 예시입니다.

인접 행렬로 dfs 구현하기

인접 행렬은 정점의 갯수만큼의 크기를 가지는 행렬을 선언한 후에 그 행렬에 간선을 저장하는 방식입니다. 어떤 정점에서 다른 정점으로 가는 간선의 존재 여부를 O(1)으로 알 수 있다는 장점이 있지만 정점의 갯수가 많을 수록 메모리를 많이 차지한다는 단점이 있습니다.

// 인접 행렬: matrix[i][j] == true라면 nodex i에서 node j로 가는 간선이 있는 것이다.
var matrix = Array(repeating: Array(repeating: false, count: N + 1), count: N + 1)
// 방문 체크 배열: check[i]가 true이면 이미 방문한 node이다.
var check = Array(repeating: false, count: N + 1)

// 간선의 입력을 받는다.
for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    matrix[edge[0]][edge[1]] = true //⭐️ 단방향 그래프라면 한쪽만
    matrix[edge[1]][edge[0]] = true //⭐️ 양방향 그래프라면 둘 다
}

// 재귀함수로 dfs 구현
func dfs(_ node: Int) {
    check[node] = true //👉 현재 node 방문 체크
    
    //✅ 다른 node들을 순회하면서
    for i in 1..<(N + 1) {
        if matrix[node][i] && !check[i] { //👉 현재 node에서 가는 간선이 존재 && 아직 미방문한 node가 존재하면
            dfs(i) //👉 그 node에서 다시 dfs를 수행한다.
        }
    }
}

인접 리스트로 dfs 구현하기

인접 리스트는 링크드 리스트로 간선을 저장하는 방식입니다. 배열 안에 정점의 갯수만큼 빈 배열을 선언해두고 간선의 반대쪽 node를 배열에 저장하는 방식입니다. 한 정점에서 다른 정점으로 가는 간선의 존재 여부를 알기위해서는 O(n)의 탐색을 해야한다는 단점이 있습니다만, 인접행렬에 비해서 메모리를 절약할 수 있다는 장점이 있습니다.

// 인접 리스트: edgeList[i]안에 j가 속해있다면 i에서 j로 가는 간선이 있는 것이다.
var edgeList = Array(repeating: [Int](), count: N + 1)
var check = Array(repeating: false, count: N + 1)

for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    edgeList[edge[0]].append(edge[1]) //👉 단방향 그래프라면 한쪽에만 추가
    edgeList[edge[1]].append(edge[0]) //👉 양방향 그래프라면 양쪽에 추가
}

// 재귀함수로 dfs 구현
func dfs(_ node: Int) {
    check[node] = true //👉 현재 node 방문 체크
    
    //⭐️ 현재 node와 연결된 정점들을 순회하면서
    for i in edgeList[node] {
        if !check[i] { //👉 아직 방문하지 않았다면
            dfs(i) //👉 dfs 실행
        }
    }
}