[백준 17471번] [Kotlin] 게리맨더링

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

17471번: 게리맨더링

 

난이도 : 골드 4
태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색

 

 

설명

 

위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다.

선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다.

 

n이 2 <= n <= 10으로, 매우 작기 때문에,그냥 각각의 구역을 1번 선거구, 2번 선거구로 나눌 수 있는 모든 경우의 수를 구한 뒤,선거구의 각 구역이 모두 서로 연결되어 있는지 확인한 후,선거구의 인원 수를 계산해주면 될 것 같습니다.

 

저 같은 경우에, 각 구역을 두 선거구로 나누는 모든 경우의 수를 구하기 위해 DFS를,각 선거구가 연결되어 있는지는 BFS를 사용하였습니다.

 

 

 

소스코드

import java.util.StringTokenizer
import kotlin.math.abs

lateinit var district: List<Int>
lateinit var connect: Array<MutableList<Int>>
lateinit var selected: Array<Boolean>
lateinit var visited: Array<Boolean>
var answer = Int.MAX_VALUE
var n = 0

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    district = readLine().split(" ").map { it.toInt() }
    connect = Array(n) { ArrayList() }
    selected = Array(n) { false }
    visited = Array(n) { false }

    for (i in 0 until n) {
        val st = StringTokenizer(readLine())
        repeat(st.nextToken().toInt()) {
            connect[i].add(st.nextToken().toInt() - 1)
        }
    }

    selectDistrict(0, 0)

    println(if (answer == Int.MAX_VALUE) -1 else answer)
}

fun selectDistrict(index: Int, depth: Int) {
    if (depth == n) {
        if (selected.all { it } || selected.none { it }) return // 두 선거구로 나눌 수 없는 경우 (모두 true 파티 or 모두 false 파티)

        visited.fill(false)

        makeParty(true) // true 선거구 연결
        makeParty(false) // false 선거구 연결

        if (visited.any { !it }) return // 연결되지 않은 구역이 있는 다음 케이스로

        val party1 = district.filterIndexed { index, _ -> selected[index] }.sum() // 선거구1 인구 수
        val party2 = district.filterIndexed { index, _ -> !selected[index] }.sum() // 선거구2 인구 수

        answer = minOf(answer, abs(party1 - party2))
        return
    }

    for (i in index until n) {
        selected[i] = true
        selectDistrict(i + 1, depth + 1)
        selected[i] = false
        selectDistrict(i + 1, depth + 1)
    }
}

fun makeParty(party: Boolean) {
    val q = ArrayDeque<Int>()

    for (i in 0 until n) {
        if (selected[i] == party) {
            q.add(i)
            visited[i] = true
            break
        }
    }

    while (q.isNotEmpty()) {
        val cur = q.removeFirst()

        connect[cur].forEach { next ->
            if (visited[next] || selected[next] != party) return@forEach
            visited[next] = true
            q.add(next)
        }
    }
}

 

 

백준시를 두 선거구로 나누어야 하기 때문에

편의상 false 선거구, true 선거구로 나누었습니다.

 

백준시의 각 구역을 두 개 선거구로 나누는 경우의 수는

DFS를 사용한 순열/조합 구하기와 비슷한 원리입니다.

단, 모두 true 선거구일 경우, 모두 false 선거구일 경우는 예외처리를 해줬습니다.

 

각 선거구 내 지역들이 모두 연결되어있는지는

DFS/BFS를 사용한 그룹화를 이용하였습니다.

 

true/false 각 선거구의 가장 index가 작은 노드를 시작으로

연결된 정점 중 같은 선거구인 구역을 방문체크 하며 탐색한 뒤,

true/false 선거구 둘 다 탐색이 끝났는데도, 방문하지 않은 선거구가 있을 경우

각 선거구의 전 구역이 직/간접적으로 연결되지 않았다고 볼 수 있습니다.

 

 

 

후기

 

https://ko.wikipedia.org/wiki/%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81

게리맨더링 - 위키백과, 우리 모두의 백과사전

 

과거 미국 사세추스주 주지사 엘브리지 게리가 투표에 유리하도록 선거구를 나눴는데,

이 모양이 마치 전설의 괴물 셀리멘더(Salamander)와 비슷하다 하여, 게리맨더라 불렀다고 합니다.

이후 이와 같이 특정 세력에 유리하게 선거구를 나누는 것을 게리맨더링이라 한다네요.

 

코딩테스트를 할 수록 여러 분야에서 새로운 지식이 늘어갑니다.