[17471] 게리멘더링

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

17471번: 게리맨더링

조합을 통한 완전탐색 + 유니온파인드로 접근하였다.

---

접근 방법

입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.

유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.

---

정답 코드

	import Foundation
	let N = Int(readLine()!)!
	var population = readLine()!.split(separator: " ").map{Int($0)!}
	var total = population.reduce(0, +)
	var edges = [(u:Int, v:Int)]()
	var ans = Int.max
	for u in 0..<N{
	let info = readLine()!.split(separator: " ").map{Int($0)!}
	let n = info[0]
	if n == 0{ continue }
	for i in 1...n{ edges.append((u,info[i]-1))}
	}
	var list = [[String]]()
	func btk(team:[String]){
	var team = team
	if team.count == N{
	list.append(team)
	return
	}
	team.append("R")
	btk(team: team)
	team.removeLast()
	team.append("B")
	btk(team: team)
	}
	btk(team: [])
	for team in list{
	var arr = population.map{-1*$0}
	var cnt = N
	var red = 0
	var blue = 0
	for i in 0..<N{
	if team[i] == "R"{
	red += population[i]
	}else{
	blue += population[i]
	}
	}
	func root(of node:Int) -> Int{
	if arr[node] < 0{ return node }
	arr[node] = root(of: arr[node])
	return arr[node]
	}
	func union(a:Int, b:Int){
	let A = root(of: a)
	let B = root(of: b)
	if team[a] != team[b] { return }
	if A==B { return }
	arr[A] += arr[B]
	arr[B] = A
	cnt -= 1
	}
	for edge in edges {
	union(a: edge.u, b: edge.v)
	}
	if cnt == 2{
	ans = min(ans,abs(red-blue))
	}
	}
	print(ans==Int.max ? -1:ans)

view raw 17471.swift hosted with ❤ by GitHub