[BOJ] 1245 농장 관리

15 May 2022

Reading time ~1 minute

농장 관리

링크: https://www.acmicpc.net/problem/1245

bfs로 해결했다.

모든 map을 순환하면서 해당하는 위치가 가장 높은 위치인지를 판단한다.
예로 map[1][2]위치를 기준으로 bfs를 순회하는데, 가장 높은 값을 자기가 가지고 있다면 true를 반환하고, 단 하나라도 더 높은 봉우리가 있다면 false를 반환해 count를 증가시키지 않는다.

이것이 가장 최적의 해결법은 아니라고 생각이 되는데, 더 좋은 방법을 추후 탐구해볼 예정이다.

정답 코드

class Boj1245 {
    companion object{
        const val arrSize = 101
        val map = Array(arrSize){Array(arrSize){0} }
        val visited = Array(arrSize){Array(arrSize){ false } }

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

        var size = Pair(0, 0)

        fun validCheck(x: Int, y: Int): Boolean
                = (x < 0|| y < 0 || x >= size.first || y >= size.second)

        fun bfs(criterionX: Int, criterionY: Int): Boolean {
            var flag = true
            val queue: Queue<Pair<Int, Int>> = LinkedList()
            visited[criterionX][criterionY] = true
            queue.add(Pair(criterionX, criterionY))

            while(queue.isNotEmpty()){
                val cur = queue.remove()

                for (i in 0 until 8) {
                    val x = cur.first + dx[i]
                    val y = cur.second + dy[i]

                    if(validCheck(x , y)) continue
                    if (map[x][y] > map[criterionX][criterionY]) flag = false
                    else if (!visited[x][y] && (map[x][y] == map[criterionX][criterionY])) {
                        queue.add(Pair(x, y))
                        visited[x][y] = true
                    }
                }
            }

            return flag
        }

        @JvmStatic
        fun main(args: Array<String>){
            val nm = readln().split(' ')
            var minValue = 987654321
            size = Pair(nm[0].toInt(),  nm[1].toInt())
            (0 until size.first).forEach{ i ->
                val arr = readln().split(' ')
                (0 until size.second).forEach { k ->
                    map[i][k] = arr[k].toInt()
                    minValue = min(map[i][k], minValue)
                }
            }
            var count = 0
            (0 until size.first).forEach{ i ->
                (0 until size.second).forEach { k ->
                    if(!visited[i][k] && map[i][k] > minValue && bfs(i, k)) count++
                }
            }

            println(count)
        }
    }
}