백준 16234번 인구 이동 - 스위프트(Swift) 풀이

---

 

1. 인접한 두 칸의 차이가 L 이상 R이하인 곳은 간선으로 연결되어있다고 생각한다.
2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다.
3. BFS가 하나도 이루어지지 않으면 이동이 끝난 것이다.

 

1. 인접한 두 칸의 차이가 L이상 R이하인 곳은 간선으로 연결되어있다고 생각한다.

 현재 상황을 그래프로 바꾸어줄 것이다. 각 칸을 정점으로 생각하고, 인접한 두 칸(정점)의 인구수 차이가 L 이상 R이하라면 두 정점을 연결해준다.

 

2. 매일 BFS로 연합을 만들고 인구 이동을 처리해준다.

 인구 이동 시뮬레이션을 진행해준다. 하루가 지날 때마다 BFS로 인접한 정점들을 연합으로 만든 뒤, 인구 이동을 처리해준다. BFS 과정에서 방문한 국가들을 배열에 담아두었다가 마지막에 배열을 순회하면서 평균 인구수로 재조정해주면 된다.

 

3. BFS가 하나도 이루어지지 않으면 이동이 끝난 것이다.

 BFS가 하나도 이루어지지 않은 날이라면 이제 이동이 끝난 것이다. 시뮬레이션을 종료하고 며칠이 지났는지 출력하면 된다.

반응형

---

import Foundation

var N = 0, L = 0, R = 0
var land = Array(repeating: [Int](), count: 50)
var visit = [[Bool]]()

typealias Pair = (row: Int, col: Int)

struct Queue {
    var queue = [Pair]()
    var front = 0
    
    var isEmpty: Bool {
        return front >= queue.count
    }
    
    mutating func push(_ p: Pair) {
        queue.append(p)
    }
    
    mutating func popFront() -> Pair {
        let ret = queue[front]
        front += 1
        return ret
    }
}

func BFS(row: Int, col: Int) -> Bool {
    var union = [Pair]()
    var sum = 0
    var queue = Queue()
    
    queue.push(Pair(row, col))
    visit[row][col] = true
    
    while !queue.isEmpty {
        let current = queue.popFront()
        let r = current.row
        let c = current.col
        
        union.append(current)
        sum += land[r][c]
        
        let adjacents = [Pair(r+1,c), Pair(r-1,c), Pair(r,c+1), Pair(r,c-1)]
        
        for adj in adjacents {
            guard (0..<N) ~= adj.row,
                  (0..<N) ~= adj.col,
                  !visit[adj.row][adj.col],
                  (L...R) ~= abs(land[r][c] - land[adj.row][adj.col]) else { continue }
            
            queue.push(adj)
            visit[adj.row][adj.col] = true
        }
    }
    
    for nation in union {
        land[nation.row][nation.col] = sum / union.count
    }
    
    return union.count != 1
}

func simulate() -> Int {
    var day = 0
    
    while true {
        var moveCount = 0
        visit = Array(repeating: Array(repeating: false, count: N), count: N)
        
        for i in 0..<N {
            for j in 0..<N {
                guard !visit[i][j] else { continue }
                let didMove = BFS(row: i, col: j)
                if didMove { moveCount += 1 }
            }
        }
        
        if moveCount == 0 { break }
        else { day += 1 }
    }
    
    return day
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    L = input[1]
    R = input[2]
    
    for i in 0..<N {
        land[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
    }
    
    let result = simulate()
    print(result)
}

solution()