[BOJ/Kotlin] 2583번 영역 구하기 : BFS

문제 설명

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

문제 풀이 아이디어

•  BFS
• 입력으로 주어지는 각 직사각형들의 시작좌표와 마지막 좌표를 이용해서 기존 BFS와 같은 0과 1로 이루어진 배열을 만들었다. 이 때 기존방식대로 풀려다 보니 그림1과 같은 모양이 뒤집힌 채로 bfs 배열에 저장된다. (본 문제에서는 상관이 없기 때문에 그대로 진행했다) 이렇게 만들어진 board에서 board값이 0으로 되어있고, 현재 방문하지 않은 칸들을 BFS 돌려 여백 부분의 갯수와 너비를 구한다. 

코드

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val input = readLine().split(" ")
    var m = input[0].toInt()
    var n = input[1].toInt()
    var k = input[2].toInt()

    var board = Array(m) { IntArray(n) }
    var visited = Array(m) { IntArray(n) { -1 } } // -1로 전체 초기화
    var queue: Queue<Pair<Int, Int>> = LinkedList()

    for (i in 0 until k) {
        var str = readLine().split(" ")
        while (true) {
            var start = Pair(str[1].toInt(), str[0].toInt())
            var end = Pair(str[3].toInt() - 1, str[2].toInt() - 1)
            for (i in start.first..end.first) {
                for (j in start.second..end.second) {
                    board[i][j] = 1
                    visited[i][j] = 1
                }
            }
            break
        }
    } // 좌표 바탕으로 1,0 bfs board 만들기
    var cnt = 0
    var width = 0
    var widthList : MutableList<Int> = mutableListOf()
    for (i in 0 until m){
        for (j in 0 until n){
            width = 0
            if (board[i][j]==0 && visited[i][j]==-1){
                cnt ++
                visited[i][j]=0
                queue.offer(Pair(i,j))
                while(queue.isNotEmpty()){
                    width ++
                    bfs(queue,board,visited,m,n)
                }
                widthList.add(width)
            }
        }
    }

    println(cnt)
    widthList.sorted().forEach{
        print("$it ")
    }
}

fun bfs(queue: Queue<Pair<Int,Int>>, board:Array<IntArray>,visited:Array<IntArray>,m:Int,n:Int){
    val dx = arrayOf(1,0,-1,-0)
    val dy = arrayOf(0,1,0,-1)
    val cur = queue.peek()
    queue.poll()
    for (i in 0 until 4){
        var nx = cur.first + dx[i]
        var ny = cur.second + dy[i]
        if (nx >= m || nx < 0 || ny >= n || ny < 0) continue
        if (visited[nx][ny] == 1 || visited[nx][ny]==0 || board[nx][ny]==1) continue
        visited[nx][ny]=0
        queue.offer(Pair(nx,ny))
    }
}

배운점

- 본 그림에서는 0,0과 1,1이 주어지면 하나의 직사각형이 색칠된다. 나는 이를 배열로 만들기 위해서 좌표말고 1칸이 0,0부터 시작되도록 만들었다. 이 때 배열은 index가 0부터 시작하기 때문에 끝 좌표는 -1한 값을 적용해줘야 함을 깨달았다.

- 문제를 마지막까지 꼼꼼히 읽어야겠다. 답의 리스트를 오름차순 혹은 내림차순으로 출력하라는 문구를 계속 놓치고 한번은 틀리는게 아쉽다.

- 프로그래머스는 입출력을 따로 안하지만 BOJ의 경우 입출력을 해야하다보니, Kotlin의 빠른 입력에 대해서 알게되었다.
바로 BufferReader를 활용해서 입력을 이용하는 것이다. readLine()과 split를 적절히 사용하는 방법을 알 수 있었다.