[백준/BOJ] 11724번 연결 요소의 개수 (Swift 스위프트)

문제 난이도: 실버 2

사용 알고리즘: DFS

 

Int 이중 배열을 통해 외부 배열은 정점의 위치를,

내부 배열은 해당 정점과 연결된 정점들을 저장한다.

 

예제 입력 1을 넣게 되면

graph는 [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]이 된다.

 

1번 정점에 연결된 정점은 2, 5

2번 정점에 연결된 정점은 1, 5

3번 정점에 연결된 정점은 4

4번 정점에 연결된 정점은 3, 6

5번 정점에 연결된 정점은 2, 1

6번 정점에 연결된 정점은 4

 

여기서 연결 요소는 [1, 2, 5], [3, 4, 6]으로 총 2개이다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]	// 정점
let m = input[1]	// 간건

var graph: [[Int]] = Array(repeating: [], count: n + 1)	// 그래프
var visited: [Bool] = Array(repeating: false, count: n + 1)	// 정점 방문 여부
visited[0] = true

var result = 0

for _ in 0 ..< m {
    
    let injacent = readLine()!.split(separator: " ").map { Int($0)! }
    
    if !graph[injacent[0]].contains(injacent[1]) {
        graph[injacent[0]].append(injacent[1])
    }
    
    if !graph[injacent[1]].contains(injacent[0]) {
        graph[injacent[1]].append(injacent[0])
    }
}

func dfs(start: Int) {
    
    visited[start] = true
    
    for nextNode in graph[start] {
        if !visited[nextNode] {
            dfs(start: nextNode)
        }
    }
}


for i in 1 ... n {
    
    if visited.contains(false) && !visited[i] {
        result += 1
        dfs(start: i)
    }
}

print(result)

 

dfs 내부 코드 풀이

start는 현재 방문하는 정점이다.

방문한 곳은 true로 바꿔주어 다시 방문할 일 없도록 한다.

 

현재 방문한 곳과 인접한 정점은 graph[start]에 모두 저장되어 있다.

이 곳에 모든 노드를 다시 방문하면 된다.

 

이때 이미 방문했던 곳은 무시한다.

 

1 ... n 코드 풀이

 

dfs를 통해 모든 곳을 방문하게되면 더 이상 실행할 필요가 없기 때문에

방문한 곳에 false가 있는지 확인했다.

 

마찬가지로 이미 방문한 정점은 다시 들어갈 필요가 없기 때문에 무시했다.

 

이렇게 되면 i가 1일 때, (1, 2, 5) 노드(정점)를 방문하게 되고 이것은 하나의 연결 요소로 볼 수 있다.

이때 result에 1을 더해줬다

 

i가 2일 때, 이미 i가 1일 때 방문 했기 때문에 건너뛴다.

 

i가 3일 때, 아직 방문하지 않았기 때문에 dfs로 들어간다.

이때 (3, 4, 6) 노드를 방문하면서 또 하나의 연결 요소를 찾을 수 있다.

 

이때 모든 노드를 모두 방문하게 되면서 더 이상 코드가 진행되지 않고 result를 출력하게 된다.