백준 - 인구이동(Swift)

백준 - 인구이동(Swift)

 

 

 문제 설명

 

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

16234번: 인구 이동

 

 나의 풀이

 

이 문제는 DFS, BFS문제다. 벽이 허물 수 있는 한 계속 허문뒤 벽들의 합을 개수로 나누어 배정하고를 반복하면 된다.

 

그리고 이를 "허물 수 있는 벽이 있을때"까지 진행하기 때문에 만약 tempMap이 기존의 map과 동일하다면 탈출해서 결과를 출력하면 된다. 

처음에는 BFS인지 바로확인하지 못하고 헤매다가 다른사람의 풀이를 보고 감을 잠았다. 벽이 허물 수 있는 것과 연합이라는 키워드를 보고 바로 떠올릴 수 있어야하는데 아직 많이 부족하다.

 

import Foundation

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

let nlr = readLine()!.components(separatedBy:" ").map{Int($0)!}
var map: [[Int]] = []
var tempMap: [[Int]] = []
var visited = [[Bool]]()
// N<=X<= R 범위
let range = nlr[1]...nlr[2]
// 인구이동이 며칠간 발생했는지
var cnt = 0
for _ in 0..<nlr[0] {
    map.append(readLine()!.components(separatedBy:" ").map{Int($0)!})
}

while true {
    tempMap = map
    visited = [[Bool]](repeating: [Bool](repeating: false, count: nlr[0]), count: nlr[0])
    for i in 0..<nlr[0] {
        for j in 0..<nlr[0] {
            guard !visited[i][j] else { continue }
            BFS(Point(i, j))
        }
    }
    if tempMap == map {
        break
    } else {
        cnt += 1
        map = tempMap
    }
}
print(cnt)

func BFS(_ p: Point) {
    var queue = [Point]()
    // 벽이 허물어지는 곳의 합
    var sum = map[p.r][p.c]
    var member = [Point]()
    var partyCount = 1
    queue.append(p)
    visited[p.r][p.c] = true
    
    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
                sum += map[next.r][next.c]
                queue.append(Point(next.r, next.c))
                partyCount += 1
            }
        }
    }
    
    for x in member {
        tempMap[x.r][x.c] = sum / partyCount
    }
}

 

 

 피드백

 

방문처리에 대해 guard문을 쓰는 것도 좋은 방법인 것 같다. 그리고 closedRange를 이용해서 패턴매칭 연산자를 사용한점과 Point의 계산속성 nexts를 사용함으로써 네가지 방면을 다룬 점을 배웠다.