[백준/BOJ] 2583번: 영역 구하기

문제

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

2583번: 영역 구하기

해설

bfs를 이용하여 푸는 문제이다.

풀이 과정을 나눠보면 다음과 같다.

• 주어지는 좌표에 해당하는 영역을 미리 체크해놓는다.
• 모든 사각형의 체크가 끝났다면, 처음부터 반복문을 실행하며 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳을 찾는다.
• 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳에 도달했다면, bfs를 수행하여 영역의 총 크기가 얼마인지 구한다.

코드를 보며 위의 과정이 어떻게 구현되었는지 확인해보자.

코드

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

private lateinit var pos: Array<BooleanArray>
private lateinit var visited: Array<BooleanArray>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var row = 0
private var col = 0
private var blockCnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    input()

    var area = 0
    val sizeList = ArrayList<Int>()
    for(i in 0 until row) {
        for(j in 0 until col) {
            if(!pos[i][j] && !visited[i][j]) {
                sizeList.add(bfs(i, j))
                area++
            }
        }
    }
    sizeList.sort()

    println(area)
    for(i in sizeList) print("$i ")
}

private fun input() = with(System.`in`.bufferedReader()) {
    val st = StringTokenizer(readLine())
    row = st.nextToken().toInt()
    col = st.nextToken().toInt()
    blockCnt = st.nextToken().toInt()

    pos = Array(row) { BooleanArray(col) }
    visited = Array(row) { BooleanArray(col) }

    repeat(blockCnt) {
        val (leftBottomX, leftBottomY, rightFloorX, rightFloorY) = readLine().split(" ").map { it.toInt() }

        for(i in leftBottomY until rightFloorY) {
            for(j in leftBottomX until rightFloorX) {
                pos[i][j] = true
            }
        }
    }
}

private fun bfs(y: Int, x: Int): Int {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(y, x))

    visited[y][x] = true

    var size = 1
    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curY = cur.first
        val curX = cur.second

        repeat(4) { i ->
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(isCheck(nextY, nextX)) {
                que.add(Pair(nextY, nextX))
                visited[nextY][nextX] = true
                size++
            }
        }
    }

    return size
}

private fun isCheck(y: Int, x: Int): Boolean
= (y in 0 until row && x in 0 until col && !visited[y][x] && !pos[y][x])