[Swift] 17471 게리맨더링 풀이 및 코드

문제 사이트

17471번: 게리맨더링

문제 요약

• N개의 구로 나누어진 시가 있다.
• 해당 시를 두 개의 구역(선거구)으로 나누어야한다.
• 한 선거구에 포함된 구역은 모두 연결되어야한다. (총 2개의 그래프로 구성돼야함)
• 이 때, 인구 차이의 최솟값을 구해라.

접근 방법

• 시를 2개의 구역으로 나눈다.
• 나누어진 선거구가 각각 연결되어있는지 확인한다.
• 인구수를 계산하여 최솟 값을 구한다.

---

접근 방법

• 시를 2개의 구역으로 나눈다.
  • 비트마스킹을 사용해서 모든 경우의 수를 구했다. 이때 n/2의 경우의 수만 계산해도 된다.
  • 왜냐하면 구가 [1], [2, 3, 4, 5]로 나누어진 것과 [2, 3, 4, 5], [1]로 나누어진 경우의 수는 동일하기 때문이다.
• 나누어진 선거구가 연결되어다면 최솟 값을 구한다.
  • BFS로 탐색한다.

---

풀이

• 그래프 입력 방법
  • input을 통해 값을 받고 맨 처음 있는 정보는 지운다. (연결된 노드의 개수는 필요 없는 정보)
  • 이후 입력받은 정보에서 -1을 하는 이유는 비트마스킹으로 받은 경우의 수가 0부터 이루어져있기 때문이다. (예시는 1번부터 n번까지로 주어지기 때문에 정보를 통일시켜야한다.)
• BFS를 다음과 같이 풀었다.
  • 매개변수에 시작노드, 해당 노드가 포함된 선거구를 매개변수로 받는다.
  • 현재 노드와 연결된 노드들 중 방문하지 않았고, 같은 선거구에 있는 경우 방문처리를 한다.
  • 구가 [1, 2, 3] [4, 5, 6] 으로 나누어져있다고 가정하면node 4와 [4, 5, 6]을 탐색한다.
  • BFS가 모두 종료된 후 모든 노드가 방문처리 되었다면, 구는 정확히 두 개로 나누어져있다고 볼 수 있다.
  • node 1과 [1, 2, 3]
• 결과 출력하는 방법
  • result의 초깃값은 Int.max로 둔다.
  • BFS를 통해 구가 정확히 두 개로 나누어졌다면 기존 result와 새로 계산한 result 중 최솟값으로 갱신한다.
  • 최종 result가 Int.max와 동일하다면 -1, 동일하지 않다면 result를 출력한다.
  • → 인구수의 최댓값이 100이므로 가능하다~!

---

코드

let n = Int(readLine()!)! // 구역의 개수
let peoples = readLine()!.split { $0 == " " }.map { Int($0)! } // 구역의 인구 수
var map = [[Int]](repeating: [], count: n)
var visited = [Bool](repeating: false, count: n)
var result = Int.max

// 그래프 입력 방법
for i in 0 ..< n {
    var input = readLine()!.split { $0 == " " }.map { Int($0)! - 1 }
    input.removeFirst()
    map[i] = input
}

var divide = divided()

for (a, b) in divide {
    
    visited = [Bool](repeating: false, count: n)
    let p1 = bfs(n: a[0], area: a)
    let p2 = bfs(n: b[0], area: b)
    
    if visited.filter({ !$0 }).isEmpty {
        result = min(result, abs(p1 - p2))
    }
}

print(result == Int.max ? -1 : result)

// 비트마스킹을 통한 경우의 수 구하기
func divided() -> [([Int], [Int])] {
    var result = [([Int], [Int])]()
    
    for i in 0 ..< (1 << n/2) { // n의 제곱, 중복 제거
        var area1 = [Int]()
        var area2 = [Int]()
        for j in 0 ..< n { // n
            if i & (1 << j) != 0 {
                area1.append(j)
            } else {
                area2.append(j)
            }
        }
        guard !area1.isEmpty && area1.count != n else { continue }
        result.append( (area1, area2))
    }
    return result
}

// bfs
func bfs(n: Int, area: [Int]) -> Int {
    var person = peoples[n]
    visited[n] = true
    
    var queue = [n]
    
    while !queue.isEmpty {
        let here = queue.removeFirst()
        
        for next in map[here] {
            if !visited[next] && area.contains(next) {
                visited[next] = true
                queue.append(next)
                person += peoples[next]
            }
        }
    }
    return person
}