프로그래머스 - 네트워크 (Lv. 3)

OQ·2022년 3월 23일
0

프로그래머스

목록 보기
25/33

문제 링크

풀이

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로 탐색해보았다.
꼬인 지문도 없었고 푸는 재미도 있었던 괜찮은 문제!

profile
덕업일치 iOS 개발자

0개의 댓글