[알고리즘] Swift -백준 #11724 (연결 요소의 개수) -DFS

문제링크

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

 

 

---

분석

방향없는 그래프에서 연결 요소의 개수를 구하시오

 

풀이 과정

노드의 개수 n, 간선의 개수 m (노드의 최대값 = 1,000 / 간선의 최대값 = 4,999,500)

간선이 적지 않기에 인접행렬을 이용하는 것이 검색속도가 빠르다

n*n의 2차원배열을 만들어 모두 0으로 초기화해준다 해당 노드가 연결되어있다면 값을 1로 변경한다

방향이 없는 그래프이므로 양방향으로 양쪽 노드 배열에 추가해준다 

(만약에 1과2가 연결되어있다고 하면 (1, 2)와 (2,1)의 값을 1로 변경한다)

재귀함수를 통해 모든 노드를 탐색하고 방문체크를 해주면서 완전탐색을 진행한다

탐색이 끝났지만 모든 노드를 탐색하지 못했다면 count를 증가시키고 다시 탐색을 진행한다

(이는 연결된 노드의 탐색이 끝났고 다른 연결된 노드가 남아있다는 뜻)

1과 연결된 노드가 2와 5가 있다면

(1, 1) = false 이므로 (1, 2) .. (1, 6)까지 확인

(1, 2) = true 이므로 2와 연결된 노드를 확인하면서 노드 2의 방문체크를 하고 2의 노드를 확인한다

(2, 1) = true 이므로 1과 연결된 노드를 확인하는데 노드 1의 방문체크를 하면 true이므로 노드확인진행을 하지 않는다

다시 (1, 5) = true 이므로 5와 연결된 노드를 확인하면서 노드 5의 방문체크를 하고 5의 노드를 확인한다

(5, 1) = true 이지만 노드 1은 방문했으므로 넘어가고 (5, 2) ...(5, 6)까지 진행한다.

여기서 5에는 (5, 2) = true 이지만 노드 2는 방문한 노드이기에 넘어간다.

1을 확인했을 때 1과 2와 5를 확인하였고 이제 확인할 노드가 없을 때

노드에 +1 을 하여 다음 노드를 확인해준다 (처음 방문노드는 1이므로 +1하면 2를 방문하고 ...6까지 방문한다)

+1한 노드는 노드 2이므로 노드 2를 방문해야 하는 데 이미 방문했던 노드이므로 바로 위의 과정을 통해 +1을 해준다

+1한 노드는 노드 3이므로 노드 3을 방문하여 위의 과정을 다시 반복한다

확인할 노드가 없을 경우에 count +1 한다. (확인할 노드가 없다는 뜻은 연결이 끊어졌다는 뜻이기 때문이다.)

 

 

풀이

let num = readLine()!.split(separator: " ").map{ Int($0)!}
let n = num[0]
let m = num[1]
//방문체크해줄 배열 //1부터 시작하기에 n+1까지 사이즈로 만든다 0은 비어있을 예정
var checkArr = [Bool](repeating: false, count: n+1)
//n+1*n+1사이즈의 인접행렬, 모두 false로 초기화
var arr = [[Bool]](repeating: Array(repeating: false, count: n+1), count: n+1)

//간선의 수만큼 반복하여 인접행렬에 값 할당
for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let u = input[0]
    let v = input[1]
    
    //방향이 없는 그래프(=양방향 그래프), 해당 노드사이의 간선이 존재하므로 값을 true로 변경
    arr[u][v] = true
    arr[v][u] = true
}

func dfs(node: Int) {
    //해당 노드와 연결되어있는 노드를 탐색
    checkArr[node] = true
    
    //0은 제외
    for i in 1...n {
        //방문하지 않은 노드이고 간선이 있는 곳이면
        if !checkArr[i] && arr[node][i] {
            //방문하지않은 노드를 탐색한다
            dfs(node: i)
        }
        //방문했던 노드였거나 간선이 없는 곳이면 간선이 있는 곳을 찾는다 (for문의 i+1)
    }
}

var count = 0
//노드를 노드의 수만큼 반복하여 탐색
for node in 1...n {
    //방문하지 않은 노드만 탐색
    if !checkArr[node] {
        count += 1
        dfs(node: node)
    }
}

print(count)

 

결과

 

 

알게된 점

아직 dfs를 구하는 방법이 헷갈려서 더 공부해야할 거 같다.

재귀함수를 어디서 부르는 지와 어떤 파라미터를 가지고 재귀를 부르는 지를 똑바로 확인해야 한다.

 

 

다른 풀이

let num = readLine()!.split(separator: " ").map{ Int($0)!}
let n = num[0]
let m = num[1]
var checkArr = [Bool](repeating: false, count: n+1)
var arr = [[Int]](repeating: [], count: n+1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let u = input[0]
    let v = input[1]
    
    arr[u].append(v)
    arr[v].append(u)
}

func dfs(node: Int) {
    checkArr[node] = true
    
    for i in 0..<arr[node].count {
        let next = arr[node][i]
        if !checkArr[next] {
            dfs(node: next)
        }
    }
}

var count = 0
//노드를 노드의 수만큼 반복하여 탐색
for node in 1...n {
    //방문하지 않은 노드만 탐색
    if !checkArr[node] {
        count += 1
        dfs(node: node)
    }
}

print(count)

2차원 배열에 간선의 노드를 원소로 추가해주는 방식

나는 인접행렬을 이용하여 해결하려 했더니 헷갈리는 부분이 많았는데 이렇게 풀면 그래도 조금 더 직관적볼 수 있는 거 같다

 

마지막으로는 스택을 이용하여 푸는 방법인데 스택을 구현해주지 않고 배열로 변경하여 풀었다.

let num = readLine()!.split(separator: " ").map{ Int($0)!}
let n = num[0]
let m = num[1]
var checkArr = [Bool](repeating: false, count: n+1)
var arr = [[Bool]](repeating: Array(repeating: false, count: n+1), count: n+1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map{ Int($0)!}
    let u = input[0]
    let v = input[1]
    
    arr[u][v] = true
    arr[v][u] = true
}


func dfs() -> Int {
    var count = 0
    var edgeArr = [Int]()
    
    for i in 1...n {
        if !checkArr[i] {
            edgeArr.append(i)
            checkArr[i] = true
            
            while !edgeArr.isEmpty {
                let tmp = edgeArr.removeLast()
                
                for j in 1...n {
                    if !checkArr[j] && arr[tmp][j] {
                        edgeArr.append(j)
                        checkArr[j] = true
                    }
                }
            }
            count += 1
        }
    }
    return count
}
print(dfs())

방법은 처음에 푼 방법과 비슷하다

배열로 하지않고 스택을 구현하여 스택에 pop과 push를 이용하고

빠른 입출력을 사용하면 시간이 훨씬 단축된다.