백준 16234 인구 이동

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

분류: BFS, DFS

---

접근방식

BFS 또는 DFS로 해결할 수 있는 문제였습니다.

주어진 범위에 해당하는 칸들을 탐색하고 그룹짓고를 반복하면 됩니다.

저는 BFS를 사용했는데요, 탐색하면서 멤버들의 따로 저장해뒀다가 탐색이 끝나기 전에 tempMap에 결과를 기록해두고

전체를 다 돌고 temp와 map을 비교해서 다시 해야할지 말지를 결정해주면서 카운트했습니다.

 

 

해결방법

struct Point {
    var r: Int
    var c: Int
    
    init(_ r: Int, _ c: Int) {
        self.r = r
        self.c = c
    }
    
    var nexts: [Point] {
        return [
            Point(r+1, c),
            Point(r-1, c),
            Point(r, c+1),
            Point(r, c-1)
        ]
    }
}

let nlr = readLine()!.split(separator: " ").map { Int(String($0))! }
var map = [[Int]]()
for _ in 0..<nlr[0] {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

let range = nlr[1]...nlr[2]
var union = 0
var visited = [[Bool]]()
var tempMap = [[Int]]()

func setParty(_ p: Point) {
    var queue: [Point] = [p]
    visited[p.r][p.c] = true
    var sum = map[p.r][p.c]
    var partyCount = 1
    var member = [Point]()
    
    while !queue.isEmpty {
        let curr = queue.removeFirst()
        member.append(curr)
        
        for next in curr.nexts where 0..<nlr[0] ~= next.r && 0..<nlr[0] ~= next.c {
            guard !visited[next.r][next.c] else { continue }
            if range ~= abs(map[curr.r][curr.c] - map[next.r][next.c]) {
                visited[next.r][next.c] = true
                queue.append(next)
                sum += map[next.r][next.c]
                partyCount += 1
            }
        }
    }
    
    for p in member {
        tempMap[p.r][p.c] = sum / partyCount
    }
}

while true {
    visited = [[Bool]](repeating: [Bool](repeating: false, count: nlr[0]), count: nlr[0])
    tempMap = map
    
    for r in 0..<nlr[0] {
        for c in 0..<nlr[0] {
            guard !visited[r][c] else { continue }
            setParty(Point(r, c))
        }
    }
    
    if tempMap == map {
        break
    } else {
        union += 1
        map = tempMap
    }
}

print(union)

 

배운점

어렵지 않은 문제였는데 구현 과정에서 생각보다 시간이 쪼끔 걸렸다...