[백준 2667번] 단지번호붙이기 - Kotlin

[백준 2667번] 단지번호붙이기 - Kotlin

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

10828번: 스택

---

문제

• <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
• 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다.
• 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.
• 대각선상에 집이 있는 경우는 연결된 것이 아니다.
• <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다.지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

---

입력

• 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력된다.
• 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

---

출력

• 첫 번째 줄에는 총 단지수를 출력하시오.
• 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

---

풀이

private class Solution2667 {
    private val directions = arrayOf(
        0 to 1,
        0 to -1,
        1 to 0,
        -1 to 0
    )

    private var count = 0

    fun solution(
        n: Int,
        map: Array<IntArray>
    ): List<Int> {
        val visited = Array(n) { BooleanArray(n) }
        val result = mutableListOf<Int>()

        for (row in map.indices) {
            for (col in map[row].indices) {
                if (!visited[row][col] && map[row][col] == 1) {
                    count = 0
                    dfs(row, col, map, visited)
                    result.add(count)
                }
            }
        }


        return result.sorted()
    }

    private fun dfs(
        row: Int,
        col: Int,
        map: Array<IntArray>,
        visited: Array<BooleanArray>
    ) {
        if (map[row][col] == 0) {
            return
        }

        visited[row][col] = true
        count += 1

        for (direction in directions) {
            val nextRow = row + direction.first
            val nextCol = col + direction.second
            val nextValue = map.getOrNull(nextRow)?.getOrNull(nextCol) ?: continue

            if (visited[nextRow][nextCol]) {
                continue
            }

            if (nextValue == 1) {
                dfs(nextRow, nextCol, map, visited)
            }
        }
    }

}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    val map = Array(n) { _ ->
        val str = br.readLine()
        IntArray(n) { col -> str[col].digitToInt() }
    }

    val result = Solution2667().solution(n, map)

    bw.append("${result.size}\n")
    for (i in result.indices) {
        bw.append("${result[i]}\n")
    }

    bw.flush()

    br.close()
    bw.close()
}