[백준] (Swift) 16234번 - 인구이동 (BFS 풀이)

✅ 문제 링크

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

16234번: 인구 이동

 

✅ 문제 풀이 아이디어

기본적으로 연합국가인지 아닌지를 판단해야하기 때문에 BFS로 풀어야한다고 생각했다. 위의 출력예제를 보면, 점선이 생기는 위치가 다르다. 

30과 40은 직접적인 연결은 아니지만, 어쨋든 연합국가이긴하다. 그렇기 때문에 초반에 어렵게만 생각되었던 "어디에 점선이생기는지 고려해야하는가"를 전혀 생각하지 않고 그냥 탐색하면서 연합국가에 같이 담아주면된다. 즉, 점선을 고려하지 않아도 된다는 이야기다!

기본 BFS 알고리즘처럼, 그래프 모두를 탐색해주면서, 연합국가의 자격이 충족되면 visited처리를 해주는 방식으로 진행했다.

 

1. BFS 알고리즘 내부에서는 L이상 R 이하의 차이를 가지고 있다면 union이라는 변수에 저장해주었다.
2. 그리고 union안에 들어가있다면, 인구수를 갱신해주어야 하기 때문에, unionPopulation을 구해서 값을 바꿔준다.
3. main코드!! BFS알고리즘의 return 값은 union.count인데, union 의 count가 2개 이상이면, 인구의 이동이 발생했다는 뜻이기 때문에 union.count가 2이상이 아닐때까지 while 문을 돌려준다.

 

✅ 전체 소스코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/16234_%EC%9D%B8%EA%B5%AC%EC%9D%B4%EB%8F%99/main.swift

GitHub - deslog/Algorithm

//
//  main.swift
//  Algorithm
//
//  Created by LeeJiSoo on 2022/07/06.
//

import Foundation

let nlr = readLine()!.split(separator: " ").map { Int(String($0))! }
var ground = [[Int]]()
let n = nlr[0]
let l = nlr[1]
let r = nlr[2]
let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1] // 상하좌우
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
for _ in 0..<n {
    ground.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

func bfs(_ i: Int, _ j: Int) -> Int {
    var queue = [(Int, Int)]()
    queue.append((i, j))
    visited[i][j] = true  // 방문처리
    var union = [(Int, Int)]()  // 연합국가 초기화하고, 다시 넣어주는 과정
    union.append((i, j))
    var count = 0  // 연합국가의 인구수를 더해주는 변수
    count += ground[i][j]
    
    while !queue.isEmpty {
        let xy = queue.removeFirst()
        let x = xy.0
        let y = xy.1
        
        for k in 0..<4 {
            let nx = x + dx[k]
            let ny = y + dy[k]
            
            if nx < 0 || nx >= n || ny < 0 || ny >= n {
                continue
            }
            
            if visited[nx][ny] {
                continue
            }
            
            // 조건 충족하면 union 에 넣어주어서 수 세어주기
            if l <= abs(ground[nx][ny] - ground[x][y]), abs(ground[nx][ny] - ground[x][y]) <= r {
                union.append((nx, ny))
                visited[nx][ny] = true
                count += ground[nx][ny]
                queue.append((nx, ny))
            }
        }
    }
    // 연합국가들의 인구 수
    let unionPopulation = Int(floor(Double(count) / Double(union.count)))
    for country in union {
        ground[country.0][country.1] = unionPopulation
    }
    
    return union.count
}

// 2. 연합국가가 2개 이상이면 bfs 통해서 계속 인구이동을 확인해야함
var day = 0
while true {
    visited = Array(repeating: Array(repeating: false, count: n), count: n) // visited 초기화
    var check = false // 인구 이동 존재 유무 체크
    
    for i in 0..<n {
        for j in 0..<n {
            if !visited[i][j] {
                if bfs(i, j) >= 2 {
                    check = true
                }
            }
        }
    }
    
    if !check { // 더이상 union 의 개수가 없는 경우 check가 false 임
        break
    }
    
    day += 1
}

print(day)