[백준/BOJ] 16234번: 인구 이동

문제

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

16234번: 인구 이동

해설

문제를 세분화해보자.

1. 인구 이동이 더 이상 일어나지 않을 때까지 반복. 즉, 우선 무한 반복을 돌린다.
2. 모든 나라를 bfs를 이용해서 연합이 가능한지 탐색한다.(dfs를 사용해도 된다.)
   • 인접 국가와의 인구 차이가 l 이상 r 이하인 경우 연합을 맺는다.
     
     • 연합 국가의 총 인원수를 갱신해준다.
     • 연합 국가의 위치 정보를 저장해준다.(나는 전역으로 list를 선언해주었다.)
     • 방문 여부를 체크해준다.
     • 큐에 연합 국가의 위치를 넣어준다.
3. bfs의 수행이 끝나 연합 국가를 모두 구했다면 각 나라의 인구수를 갱신해준다.
4. 인구 이동이 불가능할 경우 결괏값을 출력해준다.

이를 코드로 구현해보면 다음과 같다.

코드

import java.util.*
import kotlin.collections.ArrayList
import kotlin.math.abs

private var n = 0
private var l = 0
private var r = 0
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private val canMove = ArrayList<Pair<Int, Int>>()
private val que: Queue<Pair<Int, Int>> = LinkedList()
private lateinit var map: Array<IntArray>
private lateinit var visited: Array<BooleanArray>

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    l = st.nextToken().toInt()
    r = st.nextToken().toInt()

    map = Array(n) { IntArray(n) }
    repeat(n) { i ->
        st = StringTokenizer(readLine())
        repeat(n) { j ->
            map[i][j] = st.nextToken().toInt()
        }
    }

    println(move())
}

private fun move(): Int {
    var day = 0
    while(true) {
        visited = Array(n) { BooleanArray(n) }

        var isMove = false
        repeat(n) { i ->
            repeat(n) { j ->
                if(!visited[i][j]) {
                    val total = bfs(i, j)

                    if(canMove.size > 1) {
                        afterMove(total)
                        isMove = true
                    }
                }
            }
        }

        if(!isMove) return day
        day++
    }
}

private fun bfs(y: Int, x: Int): Int {
    canMove.clear()
    que.clear()

    que.add(Pair(y, x))
    canMove.add(Pair(y, x))
    visited[y][x] = true

    var total = map[y][x]
    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.first
        val curX = cur.second

        for(i in 0 until 4) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isCondition(nextY, nextX)) {
                val diff = abs(map[nextY][nextX] - map[curY][curX])
                if(diff in l .. r) {
                    que.add(Pair(nextY, nextX))
                    canMove.add(Pair(nextY, nextX))
                    total += map[nextY][nextX]
                    visited[nextY][nextX] = true
                }
            }
        }
    }

    return total
}

private fun afterMove(total: Int) {
    val avg = total / canMove.size
    for(i in canMove) map[i.first][i.second] = avg
}

private fun isCondition(y: Int, x: Int): Boolean = (y in 0 until n && x in 0 until n && !visited[y][x])