[백준]BOJ 16234 - 인구 이동 - Swift/BFS

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

16234번: 인구 이동

문제

풀이

그래프 각 원소를 전체 탐색하며, BFS를 수행하는 문제이다. 탐색할 수 있는 칸에 대한 제약조건이 문제에 제시되므로, 이에 따라 BFS를 수행하면 된다.

 

알고리즘은 다음과 같다.

1. 그래프 전체를 순서대로 순회한다. 이 때 칸이 isVisited가 false인 칸에서 bfs를 수행한다. 따라서 isVisited는 전역 변수(혹은 inout 파라미터로 전달하거나, 포인터를 쓸 수 있는 언어라면 포인터를 쓰거나...)가 되어야 한다.

2. bfs로 탐색한 칸은 서로 연합이 가능한 칸이다. bfs 탐색의 조건은 문제에 상세히 적혀있다. 그래프 전체를 순회하며 bfs 탐색을 실시하고 각 칸의 값을 조정하면, 이게 문제에서 말하는 '하루'가 지난 것이다. isVisited가 false인 칸만 연합을 수행하므로, 앞선 칸에서 수행한 bfs 탐색이 뒤에 있는 칸에 영향을 끼칠 일은 없다.

3. 1회의 인구 이동이 끝났어도 또 인구 이동이 가능할 수 있다. 따라서 1.을 더 이상 인구이동이 불가능해 질 때까지 수행한다.

 

코드

import Foundation

func bfs(root: (Int, Int)) -> Bool {
    struct Queue {
        private var queue = [(Int, Int)]()
        private var ptr = 0
        var isEmpty: Bool {
            ptr >= queue.count
        }
        mutating func insert(v: (Int, Int)) {
            queue.append(v)
        }
        mutating func delete() -> (Int, Int) {
            let popped = queue[ptr]
            ptr += 1
            return popped
        }
    }
    let moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    var queue = Queue()
    var union: [(Int, Int)] = [root]
    var unionPop = graph[root.0][root.1]
    queue.insert(v: root)
    isVisited[root.0][root.1] = true
    while !queue.isEmpty {
        let node = queue.delete()
        for move in moves {
            let newNode = (node.0 + move.0, node.1 + move.1)
            if newNode.0 < 0 || newNode.0 >= n || newNode.1 < 0 || newNode.1 >= n { continue }
            if isVisited[newNode.0][newNode.1] { continue }
            let differ = abs(graph[node.0][node.1] - graph[newNode.0][newNode.1])
            if differ >= l && differ <= r {
                isVisited[newNode.0][newNode.1] = true
                queue.insert(v: newNode)
                union.append(newNode)
                unionPop += graph[newNode.0][newNode.1]
            }
        }
    }
    let dividedPop = unionPop / union.count
    for element in union {
        graph[element.0][element.1] = dividedPop
    }
    if union.count > 1 {
        return true
    } else {
        return false
    }
}

let nlr = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, l, r) = (nlr[0], nlr[1], nlr[2])
var graph = [[Int]]()
for _ in 0..<n {
    graph.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
var isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
var answer = 0

while true {
    var isEnd = true
    for row in 0..<n {
        for column in 0..<n {
            if !isVisited[row][column] && bfs(root: (row, column)){
                isEnd = false
            }
        }
    }
    if isEnd {
       break
    }
    isVisited = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n)
    answer += 1
}
print(answer)