백준 17779 게리맨더링 2

출처: www.acmicpc.net/problem/17779

분류: 완전탐색

---

접근방식

주어진 요구사항 대로 구역을 나눠서 찾으면 되는 완전탐색 문제였습니다. 

5번 구역의 범위를 계산하는 부분에서 애를 많이 먹었습니다... 😭

 

각 구역을 구분하는 부분만 다시 보면 될 것 같은데 간단하게 살펴보겠습니다.

우선 5구역을 시작하는 점을 (pr, pc) 라고 하면,

1구역의 r, c를 검사할 때, 

c <= pc + d1 && r < pr && !( 5구역범위 )

으로 체크를 해줬습니다.

1구역에서 5구역의 r은 pr부터 pc에서 c까지의 거리만큼 대각선 위로 올라가므로

c가 pc보다 클 때 (c > p.c), pr - (c - pc) 보다 크거나 같은지로 계산해줄 수 있습니다.

if c <= p.c+d1, r < p.r, !(c > p.c && r >= p.r - (c-p.c)) {
	population[0] += map[r][c]
}

 

같은 방식으로 2구역을 생각해보면,

큰 범위는 c > pc + d1 && r <= pr-d1 + d2 && !( 5구역범위 )

5구역의 맨 위 (p.r-d1) 부터 c의 거리만큼 대각선 밑으로 내려가므로

c가 5구역의 끝보다 작을 때 (c <= pc+d1+d2), r >= p.r-d1 + ( c-(p.c+d1) ) 로 계산해줄 수 있습니다.

if c > p.c+d1, r <= p.r-d1+d2, !(c <= p.c+d1+d2 && r >= p.r-d1 + (c-(p.c+d1))) {
	population[1] += map[r][c]
}

 

같은 접근으로 3, 4 구역도 생각해주고 나머지는 5구역에 넣어줄 수 있습니다.

for r in 0..<n {
    for c in 0..<n {
        if c <= p.c+d1, r < p.r, !(c > p.c && r >= p.r - (c-p.c)) {
            population[0] += map[r][c]
        } else if c > p.c+d1, r <= p.r-d1+d2, !(c <= p.c+d1+d2 && r >= p.r-d1 + (c-(p.c+d1))) {
            population[1] += map[r][c]
        } else if c < p.c+d2, r >= p.r, !(c >= p.c && r <= p.r + (c-p.c)) {
            population[2] += map[r][c]
        } else if c >= p.c+d2, r > p.r-d1+d2, !(c <= p.c+d1+d2 && r <= p.r-d1+d2 + ((p.c+d1+d2)-c)) {
            population[3] += map[r][c]
        } else {
            population[4] += map[r][c]
        }
    }
}

 

해결방법

typealias Point = (r: Int, c: Int)
let n = Int(readLine()!)!
var map = [[Int]]()
for _ in 0..<n {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

func isInRange(_ p: Point, _ d1: Int, _ d2: Int) -> Bool {
    return (0..<n ~= p.c + d1 && 0..<n ~= p.r - d1) &&
    (0..<n ~= p.c + d2 && 0..<n ~= p.r + d2) &&
    (0..<n ~= p.c + d1 + d2 && 0..<n ~= p.r - d1 + d2) &&
    0..<n ~= p.r + d2 - d1
}

func minDiff(_ p: Point, _ d1: Int, _ d2: Int) -> Int {
    
    var population = [Int](repeating: 0, count: 5)
    
    for r in 0..<n {
        for c in 0..<n {
            if c <= p.c+d1, r < p.r, !(c > p.c && r >= p.r - (c-p.c)) {
                population[0] += map[r][c]
            } else if c > p.c+d1, r <= p.r-d1+d2, !(c <= p.c+d1+d2 && r >= p.r-d1 + (c-(p.c+d1))) {
                population[1] += map[r][c]
            } else if c < p.c+d2, r >= p.r, !(c >= p.c && r <= p.r + (c-p.c)) {
                population[2] += map[r][c]
            } else if c >= p.c+d2, r > p.r-d1+d2, !(c <= p.c+d1+d2 && r <= p.r-d1+d2 + ((p.c+d1+d2)-c)) {
                population[3] += map[r][c]
            } else {
                population[4] += map[r][c]
            }
        }
    }
    return population.max()! - population.min()!
}

var min = 40000

for r in 1..<n {
    for c in 0..<n-1 {
        for d1 in 1...r {
            for d2 in 1...n-r {
                guard isInRange((r, c), d1, d2) else { break }
                let m = minDiff((r, c), d1, d2)
                if min > m {
                    min = m
                }
            }
        }
    }
}

print(min)

 

배운점

후 5구역 체크를 못해서 몇 시간을 쓴거냐... ㅠㅠㅠㅠㅠㅠㅠㅠ