[BOJ] 17471번 : 게리맨더링(Go, Golang)

문제 링크 : 백준 17471번

[문제 접근]

풀다가 막혀서 다른 사람 코드를 참고했다.
조합을 이용해서 뽑힌 사람들이 A 선거구, 안뽑힌 사람들이 B 선거구로 나눌 수 있다.

1. A, B 선거구로 나눈다.
2. 선거구에 포함된 구역의 개수가 1개 이상인지 검사
3. 선거구에 포함된 구역들끼리 연결되어 있는지 검사(BFS를 이용)

위 조건을 다 만족하면 인구 차이를 구해서 최솟값을 정하면 된다.

[소스 코드]

package main

import (
	"bufio"
	"fmt"
	"os"
)

var r = bufio.NewReader(os.Stdin)
var w = bufio.NewWriter(os.Stdout)

var n int
var people [11]int
var arr [11][11]bool
var visit [11]bool
var ans = -1

func connection(temp []int, c bool) bool {

	var vt [11]bool
	vt[temp[0]] = true
	cnt := 1
	q := []int{temp[0]}

	for len(q) > 0 {
		x := q[0]
		q = q[1:]

		for i := 1; i <= n; i++ {
			if arr[i][x] && visit[i] == c && vt[i] == false {
				vt[i] = true
				q = append(q, i)
				cnt++
			}
		}
	}
	if len(temp) == cnt {
		return true
	}

	return false
}

func check() bool {
	var A, B []int

	for i := 1; i <= n; i++ {
		if visit[i] {
			A = append(A, i)
		} else {
			B = append(B, i)
		}
	}

	// 선거구 개수가 1개 이상
	if len(A) == 0 || len(B) == 0 {
		return false
	}

	// 선거구별로 모두 연결되어 있는지
	con1 := connection(A, true)
	con2 := connection(B, false)
	if con1 == false || con2 == false {
		return false
	}

	return true
}

// 조합 구하기
func DFS(index int, num int) {
	if num > 0 {
		if check() {
			A := 0
			B := 0

			for i := 1; i <= n; i++ {
				if visit[i] {
					A += people[i]
				} else {
					B += people[i]
				}
			}
			var num int
			if A-B > 0 {
				num = A - B
			} else {
				num = -(A - B)
			}

			if ans == -1 || ans > num {
				ans = num
			}
		}
	}

	for i := index; i <= n; i++ {
		if visit[index] {
			continue
		}
		visit[index] = true
		DFS(i, num+1)
		visit[index] = false
	}
}

func main() {

	defer w.Flush()

	fmt.Fscan(r, &n)
	for i := 1; i <= n; i++ {
		fmt.Fscan(r, &people[i])
	}
	for i := 1; i <= n; i++ {
		var a int
		fmt.Fscan(r, &a)

		for j := 0; j < a; j++ {
			var b int
			fmt.Fscan(r, &b)
			arr[i][b] = true
			arr[b][i] = true
		}
	}
	DFS(1, 0)

	if ans == -1 {
		fmt.Fprintln(w, -1)
	} else {
		fmt.Fprintln(w, ans)
	}
}