import Foundation
func solution(_ n:Int, _ computers:[[Int]]) -> Int {
let nodes = makeGraph(n, computers)
return BFS(n, nodes)
}
struct Node {
let index: Int
var connects: [Int] = []
init(_ index: Int) {
self.index = index
}
}
// 그래프 만들기
func makeGraph(_ n:Int, _ computers:[[Int]]) -> [Node] {
var nodes = (0..<n).map { Node($0) }
for (index, computer) in computers.enumerated() {
nodes[index].connects = computer
}
return nodes
}
// 네트워크 찾기
func BFS(_ n:Int, _ nodes: [Node]) -> Int {
var result = 0
var visite = (0..<n).map { _ in 0 }
for index in 0..<n where visite[index] == 0 {
result += 1 // 일단 네트워크 하나 추가
visite[index] = 1
var needVisiteIndex = [index]
while needVisiteIndex.count > 0 {
let node = nodes[needVisiteIndex.removeFirst()]
for (i, connect) in node.connects.enumerated() where connect == 1 {
if visite[i] == 0 { // 아직 가보지 못한 네트워크라면
needVisiteIndex.append(i)
visite[i] = 1
}
}
}
}
return result
}
지문 설명에 맞춰 그래프 모델을 만든다음 BFS로 탐색해보았다.
꼬인 지문도 없었고 푸는 재미도 있었던 괜찮은 문제!