[백준] #17144: 미세먼지 안녕!

• 미세먼지 확산에 따른 변화량에 대한 2차원 배열을 사용하여 변화량을 적용합니다.
• 시계방향, 반시계방향에 대한 이동에 대한 처리는 다음과 같습니다.
  • 반시계방향의 경우 시계방향(↑, →, ↓, ←)으로 이동시키면, swap 과정 없이 이동시킬 수 있습니다.
  • 시계방향의 경우 반시계방향의 경우에 대해 반대로 생각하면 됩니다.

val dx = listOf(1, 0, -1, 0)
val dy = listOf(0, 1, 0, -1)

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (r, c, t) = br.readLine().split(" ").map { it.toInt() }
    // 격자판
    val board = Array(r) { mutableListOf<Int>() }
    // 미세먼지 변화량
    val changed = Array(r) { Array(c) { 0 } }
    // 공기청정기 row
    val air = mutableListOf<Int>()

    for (i in 0 until r) {
        val col = br.readLine().split(" ").map { it.toInt() }.toMutableList()
        for (j in col.indices) {
            if (col[j] == -1) air.add(i)
        }
        board[i] = col
    }

    for (i in 0 until t) {
        // 미세먼지 변화량 초기화
        for (j in 0 until r) {
            for (k in 0 until c) {
                changed[j][k] = 0
            }
        }

        // 미세먼지 변화량 계산
        for (j in 0 until r) {
            for (k in 0 until c) {
                if (board[j][k] >= 5) {
                    val diffused = board[j][k] / 5
                    var cnt = 0
                    for (m in 0 until 4) {
                        val nx = j + dx[m]
                        val ny = k + dy[m]
                        if (nx !in 0 until r || ny !in 0 until c) continue
                        if (board[nx][ny] == -1) continue
                        changed[nx][ny] += diffused
                        cnt++
                    }
                    changed[j][k] -= diffused * cnt
                }
            }
        }

        // 공기청정기 변화량 적용
        for (j in 0 until r) {
            for (k in 0 until c) {
                board[j][k] += changed[j][k]
            }
        }

        // 공기청정기 위 방향
        for (j in air[0] - 1 downTo 1) {
            board[j][0] = board[j - 1][0]
        }
        for (j in 0 until c - 1) {
            board[0][j] = board[0][j + 1]
        }
        for (j in 0 until air[0]) {
            board[j][c - 1] = board[j + 1][c - 1]
        }
        for (j in c - 1 downTo 2) {
            board[air[0]][j] = board[air[0]][j - 1]
        }
        board[air[0]][1] = 0

        // 공기청정기 아래 방향
        for (j in air[1] + 1 until r - 1) {
            board[j][0] = board[j + 1][0]
        }
        for (j in 0 until c - 1) {
            board[r - 1][j] = board[r - 1][j + 1]
        }
        for (j in r - 1 downTo air[1]) {
            board[j][c - 1] = board[j - 1][c - 1]
        }
        for (j in c - 1 downTo 2) {
            board[air[1]][j] = board[air[1]][j - 1]
        }
        board[air[1]][1] = 0
    }

    // 총 미세먼지량
    var answer = 0
    for (i in 0 until r) {
        answer += board[i].sumOf { it }
    }
   	// 공기청정기 값 (-1, -1) 제외
    bw.write("${answer + 2}")

    br.close()
    bw.close()
}

시간복잡도

O(rct)