20057번: 마법사 상어와 토네이도 - Kotlin

20057번: 마법사 상어와 토네이도

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

 

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

 

 

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

---

 

나의 풀이

이렇게 복잡한 구현 문제는 초반에 정리만 잘 해놓는다면 생각보다 어렵지 않게 해결할 수 있습니다.

논리적인 알고리즘이 필요하지 않기 때문에 2가지만 잘 고려하면 문제를 해결할 수 있습니다.

 

 

토네이도의 이동

첫 번째는 토네이도의 이동입니다. 토네이도는 중앙에서부터 돌아가면서 이동하는데 예시를 잘 보면 규칙성이 보입니다.

 

왼 -> 아래 -> 오른 -> 위

 

위와 같은 방향으로 반복해서 이동하고 이동하는 칸은 

 

왼 1칸 -> 아래 1 칸 -> 오른쪽 2 칸 -> 위 2 칸 -> 왼 3칸 -> 아래 3칸

 

위와 같이 왼쪽과 아래를 이동한 다음 +1 오른쪽과 위를 이동한 다음 +1 이런식이 됩니다.

 

토네이도는 [0, 0] 까지 이동하는데 이는 왼쪽으로 이동했을 경우입니다. 그렇기에 탈출 조건을 이 때 넣어줍니다.

 

 

모래의 이동

두 번째는 모래의 이동입니다. 모래의 이동은 문제의 예시로 주어진 대로 진행해 보면서 방정식을 구하면 됩니다. 

이동을 왼, 아래, 오른, 위의 순서로 정해놨기 때문에 이 이동들의 합으로 몇 칸 이동할지 방향대로 구하면 됩니다.

 

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

lateinit var board: Array<IntArray>
var n = 0
var escapedSand = 0

fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()

    board = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }

    tornadoMove()

    println(escapedSand)
}

fun tornadoMove() {
    var movement = 0
    var x = n / 2
    var y = n / 2

    while (true) {
        movement++
        for (way in 0 until 2) {
            repeat(movement) {
                x += dx[way]
                y += dy[way]
                sandMove(x, y, way)
                if (x == 0 && y == 0) {
                    return
                }
            }
        }
        movement++
        for (way in 2 until 4) {
            repeat(movement) {
                x += dx[way]
                y += dy[way]
                sandMove(x, y, way)
            }
        }
    }
}




fun sandMove(x: Int, y: Int, way: Int) {
    val originalSand = board[x][y]
    var sand = board[x][y]
    board[x][y] = 0

    // 왼 * 2 - 5%
    var tempSand = originalSand * 5 / 100
    sand -= tempSand
    move(x, y, way, way, tempSand)

    // 왼 + 위쪽(왼 + 3), 왼 + 아래쪽(왼 + 1) - 10%
    tempSand = originalSand * 10 / 100
    sand -= tempSand * 2
    move(x, y, way, way + 1, tempSand)
    move(x, y, way, way + 3, tempSand)

    // 위쪽(왼 + 3), 아래쪽(왼 + 1) - 7%
    tempSand = originalSand * 7 / 100
    sand -= tempSand * 2
    moveOneTime(x, y, way + 1, tempSand)
    moveOneTime(x, y, way + 3, tempSand)


    // 위쪽(왼 + 3) * 2, 아래쪽(왼 + 1) * 2 - 2%
    tempSand = originalSand * 2 / 100
    sand -= tempSand * 2
    move(x, y, way + 1, way + 1, tempSand)
    move(x, y, way + 3, way + 3, tempSand)

    // 오른쪽(왼 + 2) + 위쪽(왼 + 3), 오른쪽(왼 + 2) + 아래쪽(왼 + 1) - 1%
    tempSand = originalSand * 1 / 100
    sand -= tempSand * 2
    move(x, y, way + 2, way + 3, tempSand)
    move(x, y, way + 2, way + 1, tempSand)

    // 왼 - 나머지
    moveOneTime(x, y, way, sand)
}

fun move(x: Int, y: Int, firstWay: Int, secondWay: Int, sand: Int) {
    val tempX = x + dx[(firstWay) % 4] + dx[(secondWay) % 4]
    val tempY = y + dy[(firstWay) % 4] + dy[(secondWay) % 4]

    if (tempX in 0 until n &&
        tempY in 0 until n) {
        board[tempX][tempY] += sand
    } else {
        escapedSand += sand
    }
}

fun moveOneTime(x: Int, y: Int, way: Int, sand: Int) {
    val tempX = x + dx[(way) % 4]
    val tempY = y + dy[(way) % 4]

    if (tempX in 0 until n &&
        tempY in 0 until n) {
        board[tempX][tempY] += sand
    } else {
        escapedSand += sand
    }
}