[백준 16236번] 아기 상어 - Kotlin

[백준 16236번] 아기 상어 - Kotlin

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

---

문제

• N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
• 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다.
• 한 칸에는 물고기가 최대 1마리 존재한다.
• 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다.
• 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
• 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
• 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
  • 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
• 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
  • 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
  • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
    • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
    • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다.
  • 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다.
• 물고기를 먹으면, 그 칸은 빈 칸이 된다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
  • 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
• 공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오

---

입력

• 첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
• 둘째 줄부터 N개의 줄에 공간의 상태가 주어진다.
• 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.
  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치
• 아기 상어는 공간에 한 마리 있다

---

출력

• 첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다

---

풀이

private class Solution16236 {
    private val directions = arrayOf(
        0 to 1,
        1 to 0,
        0 to -1,
        -1 to 0
    )

    fun solution(
        n: Int,
        map: Array<IntArray>,
        shark: Shark
    ): Int {
        var currentShark = shark
        var count = 0

        while(true){
            val visited = Array(n){ BooleanArray(n) }
            val next = bfs(n, currentShark, map, visited)

            if (next.row == currentShark.row && next.col == currentShark.col) {
                break
            } else {
                val time = currentShark.time
                currentShark = next
                currentShark.time += time
                map[currentShark.row][currentShark.col] = 0
                count += 1
            }

            if (count == currentShark.size) {
                currentShark.size += 1
                count = 0
            }

        }

        return currentShark.time
    }

    private fun bfs(
        n: Int,
        shark: Shark,
        map: Array<IntArray>,
        visited : Array<BooleanArray>
    ): Shark {
        val deque = ArrayDeque<Pair<Int,Int>>()
        visited[shark.row][shark.col] = true
        deque.add(shark.row to shark.col)

        var fishRow = Int.MAX_VALUE
        var fishCol = Int.MAX_VALUE
        var distance = 0

        while (deque.isNotEmpty()) {
            val size = deque.size
            distance += 1

            for (i in 0 until size) {
                val first = deque.removeFirst()

                for (direction in directions) {
                    val nextRow = first.first + direction.first
                    val nextCol = first.second + direction.second

                    if (nextRow !in 0 until n) {
                        continue
                    }

                    if (nextCol !in 0 until n) {
                        continue
                    }

                    if (visited[nextRow][nextCol]) {
                        continue
                    }

                    if (map[nextRow][nextCol] <= shark.size) {

                        if (map[nextRow][nextCol] in 1 until shark.size) {
                            when {
                                fishRow > nextRow -> {
                                    fishRow = nextRow
                                    fishCol = nextCol
                                }
                                fishRow == nextRow -> if (fishCol > nextCol) {
                                    fishCol = nextCol
                                }
                            }
                        }

                        visited[nextRow][nextCol] = true
                        deque.add(nextRow to nextCol)
                    }
                }
            }

            if (fishRow != Int.MAX_VALUE){
                return Shark(fishRow, fishCol, size = shark.size, distance)
            }
        }

        return shark
    }

    data class Shark(
        val row: Int,
        val col: Int,
        var size: Int = 2,
        var time: Int = 0
    )
}

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

    val n = br.readLine().toInt()
    var shark: Solution16236.Shark = Solution16236.Shark(0, 0)
    val map = Array(n) { row ->
        val nums = br.readLine().split(" ").map(String::toInt)
        IntArray(n) { col ->
            if (nums[col] == 9) {
                shark = Solution16236.Shark(row, col)
                0
            } else {
                nums[col]
            }
        }
    }

    bw.append("${Solution16236().solution(n, map, shark)}\n")
    bw.flush()

    br.close()
    bw.close()
}