[백준/BOJ] 16236번: 아기 상어

문제

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

16236번: 아기 상어

해설

bfs를 사용하여 현재 상어의 위치에서 모든 물고기들의 위치까지 거리를 구하고, 그 중 가장 거리가 가까운 물고기를 찾는다.

나는 우선 먹을 수 있는 물고기들을 전부 찾아 ArrayList에 위치와 상어와의 거리를 저장해주었다.

저장이 끝났다면 위쪽 좌표부터 시작하여 검사하여 가장 가까운 물고기가 정해지지 않는다면, 왼쪽 좌표를 검사하여 먹으러 갈 물고기를 정한다.

이제 그 위치로 가게 되고, 위의 과정을 먹을 수 있는 물고기가 없을 때까지 반복해주면 된다.

소스 코드

import java.util.*
import kotlin.collections.ArrayList

private var n = 0
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private val que: Queue<Pos> = LinkedList()
private lateinit var arr: Array<IntArray>

data class Pos(val y: Int, val x: Int, val dist: Int)

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

    arr = Array(n) { IntArray(n) }

    repeat(n) { i ->
        val st = StringTokenizer(readLine())
        repeat(n) { j ->
            arr[i][j] = st.nextToken().toInt()
            if(arr[i][j] == 9) {
                que.add(Pos(i, j, 0))
                arr[i][j] = 0
            }
        }
    }

    println(bfs())
}

private fun bfs(): Int {
    var time = 0
    var eat = 0
    var sharkSize = 2

    while(true) {
        val fish = ArrayList<Pos>()
        val dist = Array(n) { IntArray(n) }

        while(que.isNotEmpty()) {
            val cur = que.poll()
            val curY = cur.y
            val curX = cur.x

            for(i in 0 until 4) {
                val nextY = curY + dy[i]
                val nextX = curX + dx[i]

                if(checkCondition(nextY, nextX, sharkSize, dist)) {
                    dist[nextY][nextX] = dist[curY][curX] + 1
                    que.add(Pos(nextY, nextX, dist[nextY][nextX]))

                    if(canEat(nextY, nextX, sharkSize)) fish.add(Pos(nextY, nextX, dist[nextY][nextX]))
                }
            }
        }

        if(fish.isEmpty()) return time

        var curFish = fish[0]
        for(i in 1 until fish.size) {
            if(curFish.dist > fish[i].dist) {
                curFish = fish[i]
            }
            else if(curFish.dist == fish[i].dist) {
                if(curFish.y > fish[i].y) {
                    curFish = fish[i]
                }
                else if(curFish.y == fish[i].y) {
                    if(curFish.x > fish[i].x) {
                        curFish = fish[i]
                    }
                }
            }
        }

        time += curFish.dist
        eat++
        arr[curFish.y][curFish.x] = 0

        if(eat == sharkSize) {
            sharkSize++
            eat = 0
        }

        que.add(Pos(curFish.y, curFish.x, 0))
    }
}

private fun canEat(y: Int, x: Int, sharkSize: Int): Boolean {
    if(arr[y][x] in 1 .. 6 && sharkSize > arr[y][x]) return true
    return false
}

private fun checkCondition(y: Int, x: Int, sharkSize: Int, dist: Array<IntArray>): Boolean {
    if(y in 0 until n && x in 0 until n && sharkSize >= arr[y][x] && dist[y][x] == 0) return true
    return false
}