[6개월 안에 백준 플래티넘 달성하기] 13. 아기 상어 16236

아기 상어

문제

 

문제 길이가 길어서 복잡해 보이지만 조건이 생각보다 단순합니다.

다만 먹이의 우선순위를 꼼꼼하게 신경 써줘야 합니다. (상좌우하로 안됨)

 

풀이

아기 상어가 공간 내의 먹이를 다 먹을 때까지의 시간을 구하는 문제입니다.

 

문제의 조건은 다음과 같습니다

• 인접한 상하좌우로 한 칸씩 이동이 가능하다.
  • 아기 상어보다 큰 물고기가 있으면 못 지나간다.
  • 아기 상어랑 같은 크기의 물고기가 있으면 지나갈 수 있다.
  • 아기 상어보다 작은 크기의 물고기가 있으면 지나가면서 물고기를 먹을 수 있다.
• 물고기를 먹는 우선순위
  • 가장 가까운 물고기 순으로 먹는다.
  • 거리가 동일한 경우 가장 위에 있는 물고기를 먹는다.
  • 이마저도 동일하면 가장 왼쪽에 있는 물고기를 먹는다.
• 아기 상어는 자신의 크기만큼 물고기를 잡아먹으면 크기가 1 증가한다. 

 

아이디어는 다음과 같습니다.

1. bfs를 통해 가장 가까운 먹이를 찾는다.
2. 먹이가 없을 때까지 1번을 반복한다.

하지만 여기에 추가적으로 신경 써줘야 되는 부분이 있습니다. 바로 거리의 우선순위를 설정해줘야 합니다.

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

 

저는 dy, dx의 순서를 상좌우하로 설정해 주었습니다. 하지만 이런 방식으로는 우선순위가 제대로 설정되지 않습니다.

 

아래는 상좌우하로 설정할 경우 탐색 순서를 나타냅니다.

원래라면 10번째 위치가 더 위쪽에 있기 때문에 9번째 위치보다 먼저 탐색되어야 되지만 아래의 케이스는 그렇지 않습니다. (반례)

              5
           6  1  7
        8  2  0  3  10
           9  4  11
              12

 

 

따라서 결국에는 단순히 우선순위 큐를 이용해 주면 해결됩니다.

 

import java.io.StreamTokenizer
import java.util.LinkedList
import java.util.PriorityQueue

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }
    data class Pos(val y: Int, val x: Int)
    val dx = arrayOf(0,-1,1,0)
    val dy = arrayOf(-1,0,0,1)

    val N = input()
    var start = Pos(0,0)  // 시작 위치

    val arr = Array(N) { y ->
        IntArray(N) { x ->
            val a =input()
            if (a == 9) start = Pos(y, x)
            a
        }
    }

    var feedSize = 2  // 상어 크기
    var ateFeed = 0   // 먹은 물고기 개수
    var time = 0      // 시간

    fun bfs(startY: Int, startX: Int): Pos? {

        val visited = Array(N) {BooleanArray(N)}
        val pq = LinkedList<Pos>()                      
        val pq2 = PriorityQueue<Pos>(compareBy({ it.y }, { it.x })) // 먹이를 담는 큐, 우선순위 설정

        arr[startY][startX] = 0
        visited[startY][startX] = true
        pq.add(Pos(startY, startX))

        var temp = 0  // 거리
        while (pq.isNotEmpty()) {

            val size = pq.size
            repeat(size) {

                val cur = pq.poll()

                for (i in dy.indices) {
                    val nextY = dy[i] + cur.y
                    val nextX = dx[i] + cur.x

                    if (nextY !in 0..<N || nextX !in 0..<N)
                        continue
                    if (visited[nextY][nextX] || arr[nextY][nextX] > feedSize)
                        continue

                    // 이동만 가능한 경우
                    if (arr[nextY][nextX] == 0 || arr[nextY][nextX] == feedSize) {
                        visited[nextY][nextX] = true
                        pq.add(Pos(nextY, nextX))
                        continue
                    }
                    // 먹이인 경우
                    if (arr[nextY][nextX] < feedSize) {
                        visited[nextY][nextX] = true
                        pq2.add(Pos(nextY, nextX))
                    }
                }
            }
            temp++
            // 먹이를 찾은 경우
            // 현재 거리 중에서 가장 우선순위가 높은 좌표를 반환한다.
            if (pq2.isNotEmpty()) {
                time += temp
                return pq2.poll()
            }
        }
        return null
    }

    // 먹이가 없을때까지 bfs를 돌면서 먹이를 찾는다
    while (true) {
        start = bfs(start.y , start.x) ?: break
        ateFeed++
        
        // 크기만큼 물고기를 먹었을 경우 size-up
        if (ateFeed == feedSize) {  
            ateFeed = 0
            feedSize++
        }
    }

    print(time)
}