백준 17471 게리맨더링

출처: www.acmicpc.net/problem/17471

분류: 완전탐색

---

접근방식

n이 최대 10밖에 안 되기 때문에 완전탐색으로 해결할 수 있었습니다.

각 구역을 0, 1 중 하나가 되는 조합을 뽑아서

해당 조합이 조건을 만족하는지 확인하는 방식으로 해결했습니다.

 

풀이를 떠올리는 건 어렵지 않았는데 구현에서 꽤나 시간을 잡아먹었네요..

때문에 하나씩 차근차근 살펴보면서 정리해보겠습니다.

 

먼저

각 구역의 인구,
인접 구역,
파티(정당), 
최소 차이

를 담을 변수들이 필요했습니다.

구역의 최대 인구가 100이기 때문에 모든 구역의 인구가 100이여도 차이는 1000을 넘지 않습니다. 초기값은 그냥 여유롭게 10000으로 잡아줬습니다. 

var population: [Int] = [0]
var adjacent = [[Int]](repeating: [Int](), count: n+1)
var party = [Int](repeating: 0, count: n+1)
var minDifference = 10000

 

이제 각 구역의 파티를 선택해서 조합을 뽑아줘야 합니다. 

특정 개수의 조합이 아니라 배열 전부를 돌아서 파티를 결정해줘야 하기 때문에 끝에 도달했을 때 체크해줍니다.

func setParty(_ idx: Int) {
    guard idx != n else { checkPopulation(); return }
    party[idx] = 1
    setParty(idx+1)
    party[idx] = 0
    setParty(idx+1)
}

 

현재 파티 조합을 두 구역으로 나눌 수 있는지 확인해야합니다.

저는 먼저 1 구역부터 시작해서 연결된 모든 구역을 체크하고
체크가 안된 구역을 다음 구역으로 정해서 다시 연결된 모든 구역을 체크해주려고 합니다.

체크를 위해 n까지 Bool 배열 checked를 만들고, 파티를 0, 1로 설정했기 때문에 각각의 인구수를 담을 배열 [0, 0]을 만들어줍니다.
체크하면서 각 파티의 인구를 담아주고 끝나면 인구수의 차이가 현재의 최소 인구수 차이보다 작은지 확인합니다.
두 번 돌고도 아직 방문되지 않은 구역이 있다면 조건이 성립되지 않기 때문에 checked에 false가 남아있다면 걸러줍니다.

사실 이게 최선인지 잘 모르겠습니다. 더 효율적으로 풀어보고 싶었는데 저는 이게 최선이었네요

func checkPopulation() {
    var checked = [Bool](repeating: false, count: n+1)
    checked[0] = true
    
    var partySum = [0, 0]
    
    func checkParty(_ idx: Int) {
        partySum[party[idx]] += population[idx]
        
        for adj in adjacent[idx] where party[adj] == party[idx] {
            guard !checked[adj] else { continue }
            checked[adj] = true
            checkParty(adj)
        }
    }
    
    checked[1] = true
    checkParty(1)
    
    var nextParty = 2
    while nextParty <= n {
        guard !checked[nextParty] else { nextParty += 1; continue }
        checked[nextParty] = true
        checkParty(nextParty)
        break
    }
    
    let diff = abs(partySum[0] - partySum[1])
    if minDifference > diff, !checked.contains(false) {
        minDifference = diff
    }
}

 

해결방법

let n = Int(readLine()!)!

var population: [Int] = [0]
var adjacent = [[Int]](repeating: [Int](), count: n+1)
var party = [Int](repeating: 0, count: n+1)
var minDifference = 10000

for p in readLine()!.split(separator: " ").map({ Int(String($0))! }) {
    population.append(p)
}

for i in 1...n {
    let adj = [Int](readLine()!.split(separator: " ").map({ Int(String($0))! }).dropFirst())
    adjacent[i] = adj
}

func checkPopulation() {
    var checked = [Bool](repeating: false, count: n+1)
    checked[0] = true
    
    var partySum = [0, 0]
    
    func checkParty(_ idx: Int) {
        partySum[party[idx]] += population[idx]
        
        for adj in adjacent[idx] where party[adj] == party[idx] {
            guard !checked[adj] else { continue }
            checked[adj] = true
            checkParty(adj)
        }
    }
    
    checked[1] = true
    checkParty(1)
    
    var nextParty = 2
    while nextParty <= n {
        guard !checked[nextParty] else { nextParty += 1; continue }
        checked[nextParty] = true
        checkParty(nextParty)
        break
    }
    
    let diff = abs(partySum[0] - partySum[1])
    if minDifference > diff, !checked.contains(false) {
        minDifference = diff
    }
}


func setParty(_ idx: Int) {
    guard idx != n else { checkPopulation(); return }
    party[idx] = 1
    setParty(idx+1)
    party[idx] = 0
    setParty(idx+1)
}

setParty(0)
print(minDifference == 10000 ? -1 : minDifference)

 

배운점

아직도 구현력이 많이 딸리는 것 같다.

연습 또 연습 🔥🔥🔥🔥🔥🔥🔥