[문제]
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다. 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
[입력 조건]
- 첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
- 둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
- 인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
[출력 조건]
- 인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.
해결한 방법
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
private var n = 0
private var r = 0
private var l = 0
private lateinit var map : Array<IntArray>
private lateinit var visited : Array<BooleanArray>
private var result = 0
private fun main(){
val br = BufferedReader(InputStreamReader(System.`in`))
var stk = StringTokenizer(br.readLine())
n = stk.nextToken().toInt()
r = stk.nextToken().toInt()
l = stk.nextToken().toInt() // l명 이상 r명 이하
map = Array(n){ IntArray(n) }
repeat(n){ i ->
stk = StringTokenizer(br.readLine())
repeat(n){ j ->
map[i][j] = stk.nextToken().toInt()
}
}
while(true) { // 무한 반복, 0에서 n까지 모든 경우가 가능하고, 다시 연합을 해도 됨.
visited = Array(n) { BooleanArray(n) }
var flag = false
repeat(n) { i ->
repeat(n) { j ->
if (!visited[i][j]) { // 방문을 하지 않은 곳
if(bfs(i, j)){
flag = true
}
}
}
}
if(!flag){
break // bfs() 에서 true 반환이 없을 때 -> 연합 x
}
result += 1
}
print(result)
}
private fun bfs(x : Int, y: Int): Boolean {
val dx = intArrayOf(1, 0, -1, 0)
val dy = intArrayOf(0, 1, 0, -1)
val guild : MutableList<Pair<Int, Int>> = mutableListOf(Pair(x, y)) // 연합
var sum = map[x][y]
visited[x][y] = true
val q : Queue<Pair<Int, Int>> = LinkedList()
q.add(Pair(x, y))
while(q.isNotEmpty()){
val cur = q.poll()
for(i in 0 until 4){
val nx = cur.first + dx[i]
val ny = cur.second + dy[i]
if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]){
continue
}
val dif = abs(map[cur.first][cur.second] - map[nx][ny]) // 값의 차이
if(dif in r..l){
guild.add(Pair(nx, ny)) // 연합 추가
sum += map[nx][ny]
q.add(Pair(nx, ny))
visited[nx][ny] = true
}
}
}
val avg = sum / guild.size
guild.forEach{
map[it.first][it.second] = avg // 값 평균
}
return guild.size > 1 // 자신이외에 길드 나라가 없는 경우 false
}모든 나라에 대해서 BFS를 통해서 연합을 찾는다. 모든 연합을 찾으면 연합의 인구수는 연합의 평균 인구수로 변경한다. 무한 반복을 통해 연합의 인구수를 계속 조정하다가 더 이상 연합이 결성되지 않으면 지금까지 연합을 결성하는데 걸린 시간을 출력한다.
