https://www.acmicpc.net/problem/17144
문제가 매우 길다.
하지만 필드의 크기가 6~50이고 T도 최대 1000이므로 조건을 잘 맞춰 시뮬레이션만 하면 되는 문제이다.
핵심 조건들만 요약하면 아래와 같다.
- 필드의 미세먼지들은 매 초마다 확산 가능한 각 방향(필드 안이며 공기청정기가 아닌 경우)으로 (미세먼지 양) / 5 만큼 확산하고, 확산한 만큼 감소한다. (나누기 5 후 소숫점은 버림)
- 모든 미세먼지들은 동시에 확산된다 (한 곳 확산시킨 후 다음 위치 확산시키는 것이 아님)
-
공기청정기는 무조건 맨 왼쪽 열에 맨 윗행과 맨 아랫 행과 두 칸 이상 떨어져있다.
-
공기청정기는 세로로 두 칸을 차지하며, 위쪽 칸에서는 미세먼지들을 반시계 방향으로, 아래쪽 칸에서는 시계 방향으로 돌린다.
-
공기청정기는 깨끗한 공기(0)를 내보내고 공기청정기로 들어간 미세먼지는 정화된다.
-
매 초 미세먼지 확산 - 공기청정기 작동 (순환) 과정이 진행된다.
굉장히 조건이 많아 보이지만 구현해야 할 함수를 나누어 T초동안 반복해 시뮬레이션을 진행한 후 합을 구하면 된다고 생각했다.
구현해야 할 함수는 다음과 같다.
- spread함수 - 현재 필드의 미세먼지들을 규칙대로 확산시키는 작업을 진행한다.
단, 미세먼지를 동시에 확산시켜야 하므로 현재 필드를 복제한 필드를 생성해 구현한다.
이 과정을 예로 들면
먼저 배열을 두 개 준비한다 (깊은복사로)
하나를 원본으로 하고, 각 값을 확산시킨 결과를 다른 하나에 업데이트시킨다.
위에선 30을 3 방향 (왼쪽, 오른쪽, 아래)으로 6 (30/5)씩 확산시킨 것이다 (확산시키고 6*3만큼 감소).
다음은 원본의 7을, 2 방향으로 1씩 (7/5) 확산시킨다 (확산시키고 2*1만큼 감소).
다음은 원본의 10을 3 방향으로 (공기청정기 방향 확산X) 2씩(10/5) 확산시킨다. (확산시키고 3*2만큼 감소)
마지막으로 남은 20도 똑같이 진행한다.
원본 배열을 유지한 상태로 사본 배열을 조작하므로 동시에 확산시킬 수 있다.
fun spread(field: Array<Array<Int>>): Array<Array<Int>>{
val copyField = Array(field.size){Array(field[0].size){0}}
var idx = 0
for(tmp in field){
copyField[idx++] = tmp.clone()
}
for(i in field.indices){
for(j in field[i].indices){
if(field[i][j] >= 5){
val spr = field[i][j] / 5
for(d in 0..3){
val nextI = i + dir[d]
val nextJ = j + dir[d + 1]
if(nextI in field.indices && nextJ in field[i].indices && field[nextI][nextJ] != -1){
copyField[nextI][nextJ] += spr
copyField[i][j] -= spr
}
}
}
}
}
return copyField
}위에서 설명한 확산에 대한 함수 코드이다.
사본 배열을 생성한 뒤 원본 배열을 탐색해 미세먼지가 5 이상이라면 (5 미만이면 확산이 없기 때문) 상하좌우 중 확산할 수 있다면 확산시키고 현재 값을 감소시킨다.
- counterClock함수 - 공기청정기 위쪽 부분을 기준으로 반시계 방향으로 순환시키는 함수이다.
위와 같은 케이스가 있다면, 공기청정기 위쪽을 기준으로 위쪽 필드를 반시계 방향으로 돌리면 된다.
구현의 편의를 위해서 사라질 마지막 미세먼지를 기준으로 뒤에서부터 당긴다.
위와 같은 방식으로 단순하게 for문을 4번 돌려 순환을 구현하는 함수이다.
fun counterClock(field: Array<Array<Int>>, refresherTopPos: Int){
val width = field[0].size
for(i in refresherTopPos - 1 downTo 1)
field[i][0] = field[i - 1][0]
for(i in 1 until width)
field[0][i - 1] = field[0][i]
for(i in 0 until refresherTopPos)
field[i][width - 1] = field[i + 1][width - 1]
for(i in width - 1 downTo 2)
field[refresherTopPos][i] = field[refresherTopPos][i - 1]
field[refresherTopPos][1] = 0
}공기청정기 위쪽의 위치를 받아 (무조건 0열이기 때문에 y축 위치만 받음) for문 4회로 반시계 순환시킨 후 공기청정기 위쪽 바로 옆에 깨끗한 공기(0)을 내보냄
- clock 함수 - 공기청정기 아래쪽 기준으로 필드를 시계 방향으로 순환
fun clock(field: Array<Array<Int>>, refresherBotPos: Int){
val width = field[0].size
val height = field.size
for(i in refresherBotPos + 1 until height - 1)
field[i][0] = field[i + 1][0]
for(i in 1 until width)
field[height - 1][i - 1] = field[height - 1][i]
for(i in height - 1 downTo refresherBotPos + 1)
field[i][width - 1] = field[i - 1][width - 1]
for(i in width - 1 downTo 2)
field[refresherBotPos][i] = field[refresherBotPos][i - 1]
field[refresherBotPos][1] = 0
}counterClock 함수와 동일한 원리로 4회 for문을 통해 필드 아래쪽을 시계방향으로 순환시키는 함수이다.
구현에 필요한 함수를 모두 작성하였으니 시뮬레이션만 진행하면 된다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (R, C, T) = readLine().split(' ').map{it.toInt()}
var field = Array(R){readLine().split(' ').map{it.toInt()}.toTypedArray()}
var refresher = Pair(0,0)
for(i in 0 until R){
if(field[i][0] == -1){
refresher = Pair(i, i+1)
break
}
}
for(i in 1..T){
field = spread(field)
counterClock(field, refresher.first)
clock(field, refresher.second)
}
var answer = 0
for(i in field.indices){
for(n in field[i]){
if(n > 0) answer += n
}
}
print(answer)
}공기청정기 위치를 미리 저장해두고, T초만큼 spread - counterclock, clock 함수를 실행시켜 시뮬레이션을 시행한다.
이후 필드의 모든 미세먼지 값들을 더한다.
아래는 전체 코드이다.
val dir = arrayOf(-1, 0, 1, 0, -1)
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val (R, C, T) = readLine().split(' ').map{it.toInt()}
var field = Array(R){readLine().split(' ').map{it.toInt()}.toTypedArray()}
var refresher = Pair(0,0)
for(i in 0 until R){
if(field[i][0] == -1){
refresher = Pair(i, i+1)
break
}
}
for(i in 1..T){
field = spread(field)
counterClock(field, refresher.first)
clock(field, refresher.second)
}
var answer = 0
for(i in field.indices){
for(n in field[i]){
if(n > 0) answer += n
}
}
print(answer)
}
fun spread(field: Array<Array<Int>>): Array<Array<Int>>{
val copyField = Array(field.size){Array(field[0].size){0}}
var idx = 0
for(tmp in field){
copyField[idx++] = tmp.clone()
}
for(i in field.indices){
for(j in field[i].indices){
if(field[i][j] >= 5){
val spr = field[i][j] / 5
for(d in 0..3){
val nextI = i + dir[d]
val nextJ = j + dir[d + 1]
if(nextI in field.indices && nextJ in field[i].indices && field[nextI][nextJ] != -1){
copyField[nextI][nextJ] += spr
copyField[i][j] -= spr
}
}
}
}
}
return copyField
}
fun counterClock(field: Array<Array<Int>>, refresherTopPos: Int){
val width = field[0].size
for(i in refresherTopPos - 1 downTo 1)
field[i][0] = field[i - 1][0]
for(i in 1 until width)
field[0][i - 1] = field[0][i]
for(i in 0 until refresherTopPos)
field[i][width - 1] = field[i + 1][width - 1]
for(i in width - 1 downTo 2)
field[refresherTopPos][i] = field[refresherTopPos][i - 1]
field[refresherTopPos][1] = 0
}
fun clock(field: Array<Array<Int>>, refresherBotPos: Int){
val width = field[0].size
val height = field.size
for(i in refresherBotPos + 1 until height - 1)
field[i][0] = field[i + 1][0]
for(i in 1 until width)
field[height - 1][i - 1] = field[height - 1][i]
for(i in height - 1 downTo refresherBotPos + 1)
field[i][width - 1] = field[i - 1][width - 1]
for(i in width - 1 downTo 2)
field[refresherBotPos][i] = field[refresherBotPos][i - 1]
field[refresherBotPos][1] = 0
}