백준 30024번
https://www.acmicpc.net/problem/30024

문제

---

생각하기

---

• 정렬과 우선순위 큐 자료구조 개념을 익히기 좋은 문제이다.

동작

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                cornPque.offer(Corn(i, j, map[i][j]))
                isVisited[i][j] = true
            }
        }
    }

외곽부터 탐색해야 하므로 외곽의 값들이 먼저 우선순위큐에 들어간다 이렇게 되면, 외곽의 옥수수 중에서 가장 가치가 높은 옥수수의 위치가 제일 먼저 나오게된다.

private fun BFS(): String {
    val sb = StringBuilder()

    while (K-- > 0) {
        val nowCorn = cornPque.poll()

        sb.append(nowCorn.x + 1).append(' ').append(nowCorn.y + 1).append('\n')

        repeat(4) { idx ->
            val nextX = dirX[idx] + nowCorn.x
            val nextY = dirY[idx] + nowCorn.y

            if (!isAbleCheck(nextX, nextY, isVisited)) return@repeat

            isVisited[nextX][nextY] = true
            cornPque.offer(Corn(nextX, nextY, map[nextX][nextY]))
        }
    }

    return sb.toString()
} // End of BFS()

이후 외곽 옥수수에서 시작하면 상하좌우로 갈 수 있는 옥수수들이 우선순위 큐에 들어가게 되는데, 어차피 가치가 높은 순으로 정렬되기 때문에, 외곽에서 시작해서 알아서 내부로도 찾아들어가는 로직이 만들어진다.

결국 우선순위큐에 대해 이해만 하고 있다면, 굳이 외곽에서 안으로 탐색하려는 용을 쓰지 않아도 된다는 것을 알 수 있었다.

결과

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private var K = 0
private lateinit var map: Array<IntArray>
private lateinit var isVisited: Array<BooleanArray>
private lateinit var cornPque: PriorityQueue<Corn>

private val dirX = intArrayOf(0, 0, -1, 1)
private val dirY = intArrayOf(-1, 1, 0, 0)

private data class Corn(var x: Int = 0, var y: Int = 0, var value: Int = 0) : Comparable<Corn> {
    override fun compareTo(other: Corn): Int {
        return other.value - value
    }
}

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(BFS())
    bw.close()
} // End of main()

private fun BFS(): String {
    val sb = StringBuilder()

    while (K-- > 0) {
        val nowCorn = cornPque.poll()

        sb.append(nowCorn.x + 1).append(' ').append(nowCorn.y + 1).append('\n')

        repeat(4) { idx ->
            val nextX = dirX[idx] + nowCorn.x
            val nextY = dirY[idx] + nowCorn.y

            if (!isAbleCheck(nextX, nextY, isVisited)) return@repeat

            isVisited[nextX][nextY] = true
            cornPque.offer(Corn(nextX, nextY, map[nextX][nextY]))
        }
    }

    return sb.toString()
} // End of BFS()

private fun isAbleCheck(nextX: Int, nextY: Int, isVisited: Array<BooleanArray>): Boolean {
    return nextX in 0 until N && nextY in 0 until M && !isVisited[nextX][nextY]
} // End of isAbleCheck()

private fun input() {
    StringTokenizer(br.readLine()).run {
        N = nextToken().toInt()
        M = nextToken().toInt()
    }

    cornPque = PriorityQueue()
    isVisited = Array(N) { BooleanArray(M) }

    map = Array(N) {
        StringTokenizer(br.readLine()).run {
            IntArray(M) {
                nextToken().toInt()
            }
        }
    }

    for (i in 0 until N) {
        for (j in 0 until M) {
            if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
                cornPque.offer(Corn(i, j, map[i][j]))
                isVisited[i][j] = true
            }
        }
    }

    K = br.readLine().toInt()
} // End of input()