백준 [16234] kotlin

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

16234번: 인구 이동

[풀이]

bfs를 통해 탐색을 하며, L 이상 R 이하인 인접한 땅을 찾아 배열에 저장을 하고, 

탐색이 끝나면 저장한 배열을 이용하여 새롭게 인구수를 최신화를 해준다. 

 

이러한 과정을 반복하면서 인구이동이 발생이 없을 때 까지 반복한다.

 

이를 최신화를 시키는 과정을 반복한다.

[코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

lateinit var open : ArrayList<IntArray>
lateinit var arr : ArrayList<IntArray>
lateinit var sumPeople : ArrayList<Int>
lateinit var logPeople : ArrayList<Pair<Int, Int>>
var dx = listOf(0,0,1,-1)
var dy = listOf(1,-1,0,0)
var L = 0
var R = 0
var N = 0
fun main()
{
    var br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.`out`))

    var read = br.readLine().split(" ").map { it.toInt() }

    N = read[0]
    L = read[1]
    R = read[2]

    arr = arrayListOf()
    repeat(N)
    {
        i ->
        val tmp = IntArray(N,{0})
        read = br.readLine().split(" ").map { it.toInt() }
        for(j in 0 until N)
        {
            tmp[j] = read[j]
        }
        arr.add(tmp)
    }
    var ans = 0
    var find = true
    while(find)
    {
        open = ArrayList()
        repeat(N){open.add(IntArray(N,{0}))}
        var count = 0
        sumPeople = arrayListOf()
        find = false
        for(i in 0 until N)
        {
            for(j in 0 until N)
            {
                logPeople = arrayListOf()
                if(open[i][j] == 0){
                    sumPeople.add(0)
                    val people = movePeople(i,j,count+1)
                    if(people > 0){
                        count++
                        find = true
                        val npeople = (sumPeople[count - 1] + arr[i][j]) / (people + 1)
                        arr[i][j] = npeople
                        for(d in logPeople) arr[d.first][d.second] = npeople
                    }
                }
            }
        }
        if(find) ans++
    }
    println(ans)
}
fun movePeople(x : Int, y : Int, count : Int) : Int
{
    val Q = LinkedList<Pair<Int, Int>>()
    var status = 0
    Q.add(Pair(x,y))
    open[x][y] = count
    while (Q.isNotEmpty())
    {
        var pq = Q.poll()
        repeat(4)
        {
            i ->
            val nx = dx[i] + pq.first
            val ny = dy[i] + pq.second
            if(nx in 0 until N && ny in 0 until N && open[nx][ny] == 0)
            {
                if(Math.abs(arr[pq.first][pq.second] - arr[nx][ny]) in L .. R){
                    open[nx][ny] = count
                    sumPeople[count-1] += arr[nx][ny]
                    status++
                    logPeople.add(Pair(nx,ny))
                    Q.add(Pair(nx,ny))
                }
            }
        }
    }
    return status
}