[백준 21610번] [Kotlin] 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

 

난이도 : 골드 5
태그 : 구현, 시뮬레이션

 

 

설명

마법사 상어 시리즈 비바라기 편입니다.

구현 + 시뮬레이션 문제인 만큼 문제에서 주어진 내용을 그래도 구현하면 되는 문제입니다.

 

요구사항을 정리해보자면,

1. 모든 d(i) 방향으로 s(i) 칸 이동

2. 각 구름에서 비를 내린다 (구름이 있는 칸의 물의 양이 1 증가한다)

3. 물이 증가한 칸에 물복사버그 마법을 시전한다.

3-1. 물복사 버그 마법을 시전하면 대각선 거리 방향으로 거리가 1인 칸에 물이 있는 바구니의 수 만큼 물의 양이 증가한다

4. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름을 만든다.

4-1. 이 때 구름이 생기는 칸은 비가 내린 칸이 아니며, 물의 양이 2 이상인 칸이다.

5. 위 과정을 m번 반복한다

위와 같습니다.

 

 

 

 

소스코드

전체 소스코드

package baekjoon.gold.g5.`마법사 상어와 비바라기`

import java.util.StringTokenizer

data class Cloud(var x: Int, var y: Int)

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

val crossDx = arrayOf(-1, -1, 1, 1)
val crossDy = arrayOf(-1, 1, -1, 1)

var n = 0

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    val m = nm[1]

    val map = Array(n) { readLine().split(" ").map { it.toInt() }.toIntArray() }
    var clouds = arrayListOf(Cloud(n - 1, 0), Cloud(n - 1, 1), Cloud(n - 2, 0), Cloud(n - 2, 1))

    repeat(m) {
        val st = StringTokenizer(readLine())
        val (d, s) = List(2) { st.nextToken().toInt() }

        moveCloud(clouds, d, s)
        rainFall(map, clouds)
        waterCopyBug(map, clouds)
        clouds = makeCloud(map, clouds)
    }

    println(map.sumOf { it.sum() })
}

fun makeCloud(map: Array<IntArray>, prevClouds: ArrayList<Cloud>): ArrayList<Cloud> {
    val newClouds = ArrayList<Cloud>()
    for (i in 0..<n) {
        for (j in 0..<n) {
            if (map[i][j] < 2 || prevClouds.any { it.x == i && it.y == j }) continue
            newClouds.add(Cloud(i, j))
            map[i][j] -= 2
        }
    }

    return newClouds
}

fun waterCopyBug(map: Array<IntArray>, clouds: ArrayList<Cloud>) {
    clouds.forEach { cloud ->
        for (i in 0..<4) {
            val nx = cloud.x + crossDx[i]
            val ny = cloud.y + crossDy[i]

            if (nx !in 0..<n || ny !in 0..<n || map[nx][ny] == 0) continue
            map[cloud.x][cloud.y]++
        }
    }
}


fun rainFall(map: Array<IntArray>, cloud: ArrayList<Cloud>) {
    cloud.forEach { map[it.x][it.y]++ }
}

fun moveCloud(cloud: ArrayList<Cloud>, d: Int, s: Int) {
    for (i in cloud.indices) {
        cloud[i].x = (cloud[i].x + dx[d] * s) % n
        cloud[i].y = (cloud[i].y + dy[d] * s) % n

        while (cloud[i].x < 0) cloud[i].x += n
        while (cloud[i].y < 0) cloud[i].y += n
    }
}

 

 

 

dx와 dy

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

 

dx, dy는 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 방향을 넣어줬습니다.

단, d는 1~8이므로, 0번째 인덱스는 사용하지 않습니다.

 

 

 

crossDx, crossDy

val crossDx = arrayOf(-1, -1, 1, 1)
val crossDy = arrayOf(-1, 1, -1, 1)

 

물복사 버그 시전 시 대각선 방향에 있는 물 양동이를 체크할 때 사용할 dx, dy 입니다. 대각선 4방향을 담았습니다.

 

 

 

moveCloud : 구름 이동

fun moveCloud(cloud: ArrayList<Cloud>, d: Int, s: Int) {
    for (i in cloud.indices) {
        cloud[i].x = (cloud[i].x + dx[d] * s) % n
        cloud[i].y = (cloud[i].y + dy[d] * s) % n

        while (cloud[i].x < 0) cloud[i].x += n
        while (cloud[i].y < 0) cloud[i].y += n
    }
}

 

moveCloud는 구름을 이동시키는 메서드입니다.

d 방향으로 s 만큼 이동합니다.

1번째 행과 n번째 행, 1번째 열과 n번째 열은 서로 연결되어 있으므로,

모듈러 연산 및 음수일 경우 양수가 될 때 까지 n을 더해줍니다.

 

 

 

rainFall : 비 내리기

fun rainFall(map: Array<IntArray>, cloud: ArrayList<Cloud>) {
    cloud.forEach { map[it.x][it.y]++ }
}

 

구름의 각 칸에 비를 내리는 메서드입니다.

해당 칸의 양동이에 1만큼의 비가 채워집니다.

 

 

 

waterCopyBug : 물복사버그 시전

fun waterCopyBug(map: Array<IntArray>, clouds: ArrayList<Cloud>) {
    clouds.forEach { cloud ->
        for (i in 0..<4) {
            val nx = cloud.x + crossDx[i]
            val ny = cloud.y + crossDy[i]

            if (nx !in 0..<n || ny !in 0..<n || map[nx][ny] == 0) continue
            map[cloud.x][cloud.y]++
        }
    }
}

 

waterCopyBug는 물복사버그를 시전하는 메서드입니다.

대각선 4방향에 대해 물이 차 있는 양동이의 개수만큼 더해줍니다.

 

 

 

makeClound : 구름 만들기

fun makeCloud(map: Array<IntArray>, prevClouds: ArrayList<Cloud>): ArrayList<Cloud> {
    val newClouds = ArrayList<Cloud>()
    for (i in 0..<n) {
        for (j in 0..<n) {
            if (map[i][j] < 2 || prevClouds.any { it.x == i && it.y == j }) continue
            newClouds.add(Cloud(i, j))
            map[i][j] -= 2
        }
    }

    return newClouds
}

 

makeCloud는 구름을 만들어 반환하는 메서드입니다.

이전에 구름이 소멸한 칸이 아니면서, 양동이의 용량이 2 이상인 경우 구름을 생성합니다.

양동이의 양은 2를 빼줍니다.

 

 

 

후기

골드 5인 만큼, 골드 1~2 마법사 상어 시리즈에 비해 수월하게 풀렸던 것 같네요.