[프로그래머스] 위클리 챌린지 전력망을 둘로 나누기 with Swift

안녕하세요😀 오늘은 프로그래머스 전력망을 둘로 나누기 문제를 풀어보겠습니다!

 

코딩테스트 연습 - 전력망을 둘로 나누기

전력망을 둘로 나누기 문제는 완전탐색을 이용해서 풀었습니다.

 

최대 노드 갯수가 100개이기 때문에 bfs알고리즘으로 풀 경우 최악의 상황에서 O(n * nlogn) 의 시간이 걸리기 때문에 시간제한이 걸리진 않을듯 합니다!

 

이제 문제를 풀어보겠습니다!

 

wireGraph와 isVisitedNode를 선언하고 완전탐색이므로 전력망을 둘로 나누기 위해 wire를 자르는데 모든 와이어를 한번씩 잘라 봅시다!

for i in 0..<wires.count {
    var isVisitedNode:[Int] = [Int](repeating: 0, count: n+1)
    var wireGraph:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)
    
    // init
    for j in 0..<wires.count {
        if j == i {
            continue
        }
        wireGraph[wires[j][0]][wires[j][1]] = 1
        wireGraph[wires[j][1]][wires[j][0]] = 1
    }
    
    // todo: bfs algorithm
}

 

이후 bfs알고리즘을 이용해 나뉘어진 노드의 갯수를 구합니다

// count by bfs
var queue:[Int] = [1]
isVisitedNode[1] = 1

while true {
    if queue.isEmpty {
        break
    }
    
    var canGo:[Int] = [Int]()
    for j in queue {
        for k in 0..<wireGraph[j].count {
            if isVisitedNode[k] == 0 && wireGraph[j][k] == 1{
                canGo.append(k)
                isVisitedNode[k] = 1
            }
        }
    }
    
    queue = canGo
}

var nodeCount = 0
for j in isVisitedNode {
    if j == 1 {
        nodeCount += 1
    }
}

 

그리고 각각의 wire를 자를때마다 최소 차이값을 answer에 저장해둡니다.

let currentAnswer = abs((n - nodeCount) - (nodeCount))
if currentAnswer < answer {
    answer = currentAnswer
}

 

이렇게 answer를 반환해주면 문제가 해결됩니다!

import Foundation

func solution(_ n:Int, _ wires:[[Int]]) -> Int {
    
    var answer = n + 1
    
    for i in 0..<wires.count {
        var isVisitedNode:[Int] = [Int](repeating: 0, count: n+1)
        var wireGraph:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)
        
        // init
        for j in 0..<wires.count {
            if j == i {
                continue
            }
            wireGraph[wires[j][0]][wires[j][1]] = 1
            wireGraph[wires[j][1]][wires[j][0]] = 1
        }
        
        // count by bfs
        var queue:[Int] = [1]
        isVisitedNode[1] = 1
        
        while true {
            if queue.isEmpty {
                break
            }
            
            var canGo:[Int] = [Int]()
            for j in queue {
                for k in 0..<wireGraph[j].count {
                    if isVisitedNode[k] == 0 && wireGraph[j][k] == 1{
                        canGo.append(k)
                        isVisitedNode[k] = 1
                    }
                }
            }
            
            queue = canGo
        }
        
        var nodeCount = 0
        for j in isVisitedNode {
            if j == 1 {
                nodeCount += 1
            }
        }
        
        let currentAnswer = abs((n - nodeCount) - (nodeCount))
        if currentAnswer < answer {
            answer = currentAnswer
        }
    }
    
    return answer
}

오늘은 여기까지입니다!

 

질문이 있으시면 댓글로 남겨주세요!

 

오늘도 좋은 하루 되세요~