백준 - 그림(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/2468

 

[문제 설명]

그림의 개수와 가장 큰 그림의 크기를 구하여라

 

[접근 방법]

그래프 탐색 문제. 그냥 그래프 탐색하면 됩니다.

단, 그림이 없는 경우의 크기는 0입니다.

저는 이를 파악 못하고 그림 크기를 Int의 최솟값으로 초기화하여 처음에 통과하지 못했습니다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.StringTokenizer

fun main() {
    var maxSize = 0
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    // length of height
    val n = st.nextToken().toInt()
    // length of width
    val m = st.nextToken().toInt()
    val visited = Array(n) { BooleanArray(m) }
    val map = Array(n) { IntArray(m) }

    repeat(n) { row ->
        st = StringTokenizer(br.readLine())
        repeat(m) { col ->
            map[row][col] = st.nextToken().toInt()
        }
    }

    var cntOfPicture = 0
    for (r in map.indices) {
        for (c in map[r].indices) {
            if (visited[r][c] || map[r][c] == 0) {
                continue
            }

            cntOfPicture++
            maxSize = maxSize.coerceAtLeast(getPictureSize(visited, map, r, c))
        }
    }

    bw.write("$cntOfPicture\n")
    bw.write("$maxSize")
    bw.flush()
}

fun getPictureSize(visited: Array<BooleanArray>, map: Array<IntArray>, r: Int, c: Int): Int {
    var currentSize = 0
    val dy = intArrayOf(-1, 0, 1, 0)
    val dx = intArrayOf(0, 1, 0, -1)
    val queue = LinkedList<Pair<Int, Int>>()
    queue.offer(r to c)
    visited[r][c] = true

    while (queue.isNotEmpty()) {
        val node = queue.poll()
        currentSize++

        for (i in dy.indices) {
            val nextY = node.first + dy[i]
            val nextX = node.second + dx[i]

            if (nextY in map.indices && nextX in map[0].indices) {
                if (visited[nextY][nextX] || map[nextY][nextX] == 0) {
                    continue
                }
                visited[nextY][nextX] = true
                queue.offer(nextY to nextX)
            }
        }
    }

    return currentSize
}