[Swift 알고리즘] 백준 BOJ - 11724 연결 요소의 개수

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "11724 연결 요소의 개수" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

11724번: 연결 요소의 개수

 

---

풀이

오늘은 그래프 문제를 풀어봤습니다.

 

전형적인 그래프 문제로 연결 요소의 개수를 세는 문제입니다.

즉, 연결된 그래프의 개수를 세면 됩니다.

 

dfs, bfs 모두 사용할 수 있는데요. 저는 스택을 이용한 dfs를 사용했습니다.

연결 요소가 시작될 때 +1을 해줍니다. dfs를 이용해 탐색할 수 있을 때까지 탐색합니다.

요소가 끝나면 방문하지 않은 요소를 찾아 있다면 다시 dfs를 이용해 탐색합니다.

 

코드를 보며 설명을 함께 보면 좋을 것 같습니다.

 

---

전체 코드

//11724 연결 요소의 개수
import Foundation

let inputs = readLine()!.split(separator: " ").map { Int(String($0))! }
let edges = inputs[0]
let lines = inputs[1]

var graph: [Int: [Int]] = [:]
var visitNode: [Int] = []
var needVisitNode: [Int] = []

for edge in 1...edges {
    graph.updateValue([], forKey: edge)
}

for _ in 0..<lines {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[input[0]]?.append(input[1])
    graph[input[1]]?.append(input[0])
}

var result: Int = 0
for i in 1...edges {
    if visitNode.contains(i) {
        continue
    }
    
    result += 1
    
    needVisitNode.append(i)
    while !needVisitNode.isEmpty {
        let node = needVisitNode.popLast()!
        if !visitNode.contains(node) {
            visitNode.append(node)
            needVisitNode.append(contentsOf: graph[node] ?? [])
        }
    }
}

print(result)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.