백준 17471 - 게리맨더링 (Go)

17471번: 게리맨더링

문제 내용은 위 링크에서

풀이 방법

1. 선거구를 두개로 나눈다.

2. 나눠진 두 선거구의 각 구역이 전부 연결되어있는지 확인한다. (bfs이용)

3. 각 구역이 전부 연결되어있는 경우 두 선거구의 인구수 차이를 확인한다.

4. 계산한 인구수가 기존의 결과보다 작으면 결과값을 갱신한다.

5. 선거구를 나누는 모든 경우의 수에 대하여 1~4 과정을 반복한다.

 

풀이 코드

// https://www.acmicpc.net/problem/17471

package main

import (
    "fmt"
)

const max int = int(^(uint(0)) >> 1)

func checkConnect(a []bool, connect [][]bool) bool {
    as := []int{}
    bs := []int{}
    for i := range a {
        if a[i] {
            as = append(as, i)
        } else {
            bs = append(bs, i)
        }
    }
    return bfs(as, connect) && bfs(bs, connect)
}

func calcPopulation(a []bool, pop []int) int {
    var aSum, bSum int
    aSum = 0
    bSum = 0
    for i := range a {
        if a[i] {
            aSum += pop[i]
        } else {
            bSum += pop[i]
        }
    }
    ret := aSum - bSum
    if ret >= 0 {
        return ret
    }
    return -ret
}

func search(wardPop []int, connect [][]bool) int {
    var a []bool
    ret := max
    a = make([]bool, len(wardPop))
    for bitCounter := uint(0); bitCounter < 1<<uint(len(wardPop)); bitCounter++ {
        for i := 0; i < len(wardPop); i++ {
            if ((1<<uint(i))&bitCounter)>>uint(i) == 1 {
                a[i] = true
            } else {
                a[i] = false
            }
        }

        if checkConnect(a, connect) {
            calc := calcPopulation(a, wardPop)
            if ret > calc {
                ret = calc
            }
        }
    }
    if ret == max {
        return -1
    }
    return ret
}

func bfs(a []int, connect [][]bool) bool {
    if len(a) == 0 {
        return false
    }
    searched := make([]bool, len(connect))
    searched[a[0]] = true
    queue := []int{a[0]}
    for len(queue) > 0 {
        var u = queue[0]
        queue = append(queue[:0], queue[1:]...)
        for j := range connect[u] {
            if connect[u][j] && searched[j] == false {
                var flag = false
                for _, value := range a {
                    if value == j {
                        flag = true
                    }
                }
                if flag {
                    searched[j] = true
                    queue = append(queue, j)
                }
            }
        }
    }
    for _, v := range a {
        if !searched[v] {
            return false
        }
    }
    return true
}

func main() {
    var n int
    var connect [][]bool
    var wardPop []int
    fmt.Scan(&n)
    connect = make([][]bool, n)
    wardPop = make([]int, n)
    for i := range connect {
        connect[i] = make([]bool, n)
    }
    for i := 0; i < n; i++ {
        fmt.Scan(&wardPop[i])
    }
    for i := 0; i < n; i++ {
        var cn int
        fmt.Scan(&cn)
        for j := 0; j < cn; j++ {
            var tmp int
            fmt.Scan(&tmp)
            connect[i][tmp-1] = true
        }
    }
    fmt.Printf("%d\n", search(wardPop, connect))
}

 

 

코드 설명

main()함수에서 입력을 받고. search()함수를 통해서 계산을 한다.

search()함수에서는 총 N개의 구역에서 n개의 구역을 뽑아, 뽑힌 구역과 뽑히지 않은 구역으로 선거구를 두개로 나눈다. 선거구는 bitCounter의 i번째 비트가 1이면 선택된 선거구, 0이면 선택되지 않은 선거구로 표기하였다. 이를 통해서 N개의 선거구에서 뽑힐 수 있는 모든 조합을 얻을 수 있게 하였다.

나눈 선거구에서 checkConnect()함수로 선거구의 구역이 전부 연결이 되었는지 확인하고, 전부 연결이 되어있으면 calcPopulation()함수에서 두 구역의 인구수 차이를 계산하여, 해당 값이 최소값이 되도록 한다.

checkConnect()함수에서는 i번째가 선택된 선거구면 슬라이스 as에 i값을 넣고, 선택되지 않은 선거구라면 슬라이스 bs에 i값을 넣었다. 이후 bfs()함수를 통해 그래프 순회를 하며 선거구의 모든 구역이 연결되어있는지 확인하여 두 선거구 모두 각 구역이 연결되어있으면 true를 return하고, 그렇지 않다면 false를 return한다.

bfs()함수에서는 너비 우선 탐색을 진행하며 입력받은 슬라이스에 있는 모든 구역들이 서로 연결되어있는지 확인하여 연결되어있으면 true, 연결되어있지 않으면 false를 return한다.

calcPopulation()함수에서는 선택된 선거구의 인구수를 aSum에 선택되지 않은 선거구의 인구수를 bSum에 저장하고, 그 차이의 절댓값을 return한다.

상수 max에는 signed int의 최댓값이 들어있는데, 두 구역으로 나눌 수 있는 경우, 두 구역의 인구수의 차이의 최댓값은, 문제 조건에서 N의 최댓값이 10, 구역의 인구수의 최솟값이 1, 최댓값은 100이므로, 인구수 1인 구역 1개 / 인구수 100인 구역 9개로 나눴을 때 899이다. 따라서 두 구역의 인구수 차이가 상수 max와 같다면, 두 구역으로 나눌 수 없다는 의미이므로 -1을 return한다.

 

 

특이사항

Go 언어에서 비트 이동 연산자인 <<와 >>를 사용 할 때, 현재 이용중인 1.13.4 windows/amd64 버전에서는 int를 사용 가능했으나, 채점서버에서 사용하는 1.11.2 linux/amd64 버전에서는 unsigned int만 사용가능하여 컴파일 에러가 났었음.

 

추가 성능 향상 방법

구역이 1, 2, 3, 4, 5와 같이 되어있을 때, 1, 2, 3을 뽑는 경우와 4, 5를 뽑는 경우가 사실상 같으나 이 코드의 경우 두가지를 모두 계산한다. 따라서 조합을 뽑는 방법을 개선하면 bfs()함수의 호출 횟수가 절반으로 줄어들어 그만큼의 성능 향상을 기대할 수 있다.