[백준/BOJ] 1926번: 그림

문제

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

1926번: 그림

해설

그림이 그려진 영역의 개수와 가장 큰 영역의 넓이를 출력하는 문제이다.

bfs를 통해 문제를 풀 수 있다.

입력을 모두 받고, 2중 반복문을 수행하며 아직 방문하지 않은 1이 찾는다.

이러한 1을 찾았다면, bfs를 수행시켜 그림의 영역을 구한다.

그림의 영역을 구하면서 방문 여부 처리를 해주며 이 칸에 또 방문했을 때 bfs를 수행할 일이 없도록 해준다.

이처럼 아직 방문하지 않은 1을 찾을 때마다 그림의 수를 증가시켜주고, bfs를 수행하여 얻은 그림의 영역이 더 큰 값을 저장한다.

마지막으로 그림의 수, 가장 큰 넓이를 출력하면 된다.

코드

import java.util.*
import kotlin.math.max

private lateinit var arr: Array<IntArray>
private lateinit var visited: Array<BooleanArray>
private val dx = intArrayOf(1, -1, 0, 0)
private val dy = intArrayOf(0, 0, 1, -1)
private var n = 0
private var m = 0

fun main() = with(System.`in`.bufferedReader()) {
    var st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()

    arr = Array(n) { IntArray(m) }
    visited = Array(n) { BooleanArray(m) }

    repeat(n) { i ->
        st = StringTokenizer(readLine())
        repeat(m) { j ->
            arr[i][j] = st.nextToken().toInt()
        }
    }

    
    var cnt = 0
    var maxArea = 0
    for(i in 0 until n) {
        for(j in 0 until m) {
            if(arr[i][j] == 1 && !visited[i][j]) {
                cnt++
                maxArea = max(maxArea, bfs(i, j))
            }
        }
    }

    println(cnt)
    println(maxArea)
}

private fun bfs(y: Int, x: Int): Int {
    var area = 1
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(y, x))
    visited[y][x] = true

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

        for(i in 0 until 4) {
            val nextY = curY + dy[i]
            val nextX = curX + dx[i]

            if(!inRange(nextY, nextX)) continue
            if(visited[nextY][nextX]) continue
            if(arr[nextY][nextX] != 1) continue

            visited[nextY][nextX] = true
            que.add(Pair(nextY, nextX))
            area++
        }
    }
    return area
}

private fun inRange(y: Int, x: Int): Boolean = y in 0 until n && x in 0 until m