백준 17471, 게리맨더링 조합, 완전탐색 swift 문제풀이

 

 

 

오늘은 오랫만에 백준 문제를 하나 풀어봤습니다. solved.ac 기준, 골드5 티어 수준의 게리맨더링 문제입니다. 해당 문제는 모든 경우의 수에 대해 BFS, DFS 등의 탐색을 활용해서 N개의 구역 중 완벽하게 2개 선거구으로 나뉘는 경우에 한해 두 구역 인구수가 최솟값인 경우를 찾는 문제였습니다. 

바로 제 소스코드를 보면서 문제풀이 보도록 하겠습니다.

 

---

백준알고리즘 17471번 문제, 게리맨더링 조합 및 완전탐색 swift 문제풀이
1) 문제 입력준비 및 변수 선언하기

먼저, 입력받기전, readLine() 입력 속도 최적화를 살짝 진행한 readInput 클로져 함수를 정의해두었습니다. 위 클로져는 양수값만 입력으로 들어올때 사용할 수 있습니다. 음수도 들어가는 경우, "-" 문자에 대한 flag 예외처리도 진행해야합니다. 본 문제에서는 양수 Int값만 들어오므로 위 코드로도 충분합니다.

 

 

19 ~ 22행) 구역의 수, N을 입력 받습니다. population은 1 ~ N 구역의 인구수를 기록할 배열입니다. 1부터 시작해서 계산할 것이므로, 1부터 인덱스가 시작되도록 임의의 쓰레기값, 0을 미리 넣어두었습니다. 이후 구역의 인구수값을 입력받아 population에 추가로 저장합니다. visitCnt는 각각의 경우의 수에 대해 방문한 구역의 수를 체크하는데 사용합니다.

23행) perm 배열은 2개의 선거구로 나누는 모든 경우의 수를 체크하는데 사용합니다. 이 배열에는 0, 1 두개의 값만 들어가며, perm[2] == 0 는 2번 구역의 선거구가 0임을 의미합니다. 각각의 케이스에 대해 현재 구역에 인접한 구역이 서로 다른 선거구인지 체크하는데 사용합니다.

24행) G는 구역 간 인접 관계를 기록하는데 사용하는 인접리스트입니다. Ans는 최종적인 두개 선거구 간 최솟 인구수값이 들어갑니다.

 

 

---

2) 완전탐색으로 정답 도출하기

27 ~ 29행) 말그대로 구현할 로직을 주석으로 순서대로 정리했습니다. DFS로 모든 경우의 수 조합을 만들며 각 경우의 수에 대한 선거구 분리 가능 여부, 선거구 간 인구수 최솟값을 도출합니다.

30 ~ 44행) 두개로 선거구가 나뉠 수 있는 모든 경우의 수를 DFS로 탐색합니다. perm의 1 ~ N번째 인덱스를 0, 1로 고를 수 있는 모든 경우의 수를 탐색하면서 최소 1개 이상이 선거구 1로 선택되어있을 경우에 대해 인구수를 체크합니다.

 

 

 

 

47행) chk는 각 구역을 방문했는지 여부를 체크하는데 사용합니다.

48 ~ 62행) DFS로 돌린 모든 경우의 수에 대해서 각각 선거구가 2개로 나뉘어지는지, 이때 모든 구역이 방문이 가능한지를 체크합니다. 구역 별로 BFS를 돌려서 각 선거구에서 인접한 구역들을 방문해주면서 방문한 구역의 수, 생기는 선거구의 수를 확인합니다.

63 ~ 67행) 만약 나뉘어지는 선거구가 2개가 아니거나, 모든 구역을 방문하지 못했다면, -1을 반환해서 불가능한 경우임을 DFS 메서드에 알려줍니다. 만약 성립가능한 경우라면 2개 구역의 인구수 차이값을 반환해서 DFS메서드 내에서 최솟값과 비교하는데 사용합니다.

 

 

 

 

위에서 말했듯이, 각 선거구에서 인접한 구역들을 방문해주면서 방문한 구역의 수, 생기는 선거구의 수를 확인하는 BFS 메서드입니다. cursor, 와 배열큐를 이용해서 큐 자료구조와 비슷한 성능으로 BFS를 동작하도록 구현했습니다. 이미 방문하지 않았고, 동일 선거구인 구역에 한해서 너비우선탐색을 수행해줍니다.

 

 

 

 

앞서 구현했던 readInput 클로져를 사용해서 입력을 받고, G 이차원배열을 구성해줍니다. 이후 DFS로 구역이 나뉠 수 있는 모든 경우의 수를 돌려서 선거구 간 인구수 차이 최솟값을 도출합니다. 만약 Ans값이 여전히 Int.max라면, 이는 선거구를 두개로 완벽히 나누는 경우의수가 없음을 의미하므로 -1를 출력해줍니다.

 

 

 

---

지금까지 백준 17471, 게리맨더링 알고리즘문제를 풀어봤습니다. 이문제의 조합돌리는 방식이 익숙하지 않으시다면, 백준의 N과 M 재귀문제 시리즈를 연습하시면 좋습니다. 그와 더불어 기본적인 BFS, DFS 문제에 익숙하다면 풀 수 있는 문제였습니다.

관련 의견이나 지적 환영합니다. 그럼 이만, 즐거운 코딩되세요.

 

---

문제풀이 전체 swift 소스코드

import Foundation

func boj17471() {
    let readInput: (() -> [Int]) = {
        var temp = 0
        var result: [Int] = []
        readLine()!.forEach { char in
            if char == " " {
                result.append(temp)
                temp = 0
                return
            }
            
            temp = temp * 10 + Int(char.asciiValue!) - 48
        }
        result.append(temp)
        return result
    }
    
    let N = readInput().first!
    var population = [0]
    var visitCnt = 0
    population += readInput()
    var perm = [Int](repeating: 0, count: N+1)
    var G = [[Int]](repeating: [Int](), count: N+1)
    var Ans = Int.max
    
    // 1) DFS로 조합을 돌린다.
    // 2) 2개의 구역으로 나뉘는지 체크한다.
    // 3) 인구수 차이를 계산하여 최솟값과 대조한다.
    func DFS(_ idx: Int, _ pickCnt: Int) {
        if pickCnt >= 1 {
            let result = checkPopulation()
            if result >= 0 {
                Ans = Ans > result ? result : Ans
                if Ans == 0 { print(0); exit(0) }
            }
        }
        
        if idx > N { return }
        for jdx in idx...N {
            perm[jdx] = 1
            DFS(jdx + 1, pickCnt + 1)
            perm[jdx] = 0
        }
    }
    
    var chk = [Bool](repeating: false, count: N+1)
    func checkPopulation() -> Int {
        var divCnt = 0
        var popList = [Int]()
        visitCnt = 0
        chk = [Bool](repeating: false, count: N+1)
        for start in (1...N) {
            if chk[start] { continue }
            let pop = BFS(start: start)
            divCnt += 1
            if divCnt > 2 { return -1 }
            if pop >= 0 {
                popList.append(pop)
            }
        }
        
        if divCnt != 2 || visitCnt != N { return -1 }
        var diff = popList[0] - popList[1]
        diff = diff > 0 ? diff : diff * -1
        return diff
    }
    
    func BFS(start: Int) -> Int {
        var popResult = population[start]
        var queue: [Int] = [start]
        chk[start] = true
        visitCnt += 1
        var cur = 0
        while cur < queue.count {
            let now = queue[cur]
            cur += 1
            G[now].forEach { next in
                if chk[next] || perm[start] != perm[next] { return }
                chk[next] = true
                visitCnt += 1
                popResult += population[next]
                queue.append(next)
            }
        }
        
        return popResult
    }
    
    (1...N).forEach { num in
        let ip3 = readInput()
        ip3[1...].forEach { otherN in
            G[num].append(otherN)
        }
    }
    
    DFS(1, 0)
    print(Ans == Int.max ? -1 : Ans)
}