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

Problem

 

코딩테스트 연습 - 9주차

---

Solution

 

1. 전선망의 연결 정보를 connect 이중배열을 만들어서 저장한다.

 

 var connect = Array(repeating: Array(repeating: false, count: n+1), count:n+1)

wires.forEach {
        connect[$0[0]][$0[1]] = true
        connect[$0[1]][$0[0]] = true
    }

 

2. 연결된 전선을 하나씩 잘라보며 왼쪽과 오른쪽의 갯수를 세주고 최솟값과 비교합니다.

 

우선 최솟값을 저장하는 minCount 변수를 만들어줍니다.

 

만약 1과 3이 연결되어 있다면 이 연결을 끊고 1과 연결된 전선의 갯수(leftCount)와

 

3과 연결된 전선의 갯수(rightCount)를 뺀 값과 최솟값을 비교하여 더 작은 값을 최솟값으로 만들어줍니다.

 

var minCount:Int = Int.max

wires.forEach {
        var leftCount:Int = 0
        var rightCount:Int = 0
        countConnectingWire(parent: nil, start: $0[0],stop: $0[1], count: &leftCount,connect: connect)
        countConnectingWire(parent: nil, start: $0[1],stop: $0[0] ,count: &rightCount,connect: connect)
        minCount = min(minCount,abs(leftCount-rightCount))
    }

 

3. dfs로 특정 전선이 다른 전선과 연결된 갯수를 세준다.

 

위에서 저장한 connect 정보를 통해서 연결된 전선을 필터링 해줍니다.

 

무한루프를 막기 위해 바로 그 전 노드(parent)와 stop(왼쪽의 전선일 경우 오른쪽,오른쪽의 전선일 경우 왼쪽)일 경우를

 

제외한 갯수를 count에 더해줍니다.

 

func countConnectingWire(parent:Int?,start:Int,stop:Int,count:inout Int,connect:[[Bool]]) {
    let filter = connect[start].enumerated().filter{$0.element && $0.offset != parent && $0.offset != stop}.map{$0.offset}
    count += filter.count
    filter.forEach {
        countConnectingWire(parent:start,start: $0, stop: stop, count: &count,connect: connect)
    }
}

 

4. 최솟값을 반환합니다.

 

    return minCount

---

Source Code