[백준] 2667번: 단지번호붙이기 - Kotlin[코틀린]

문제

 

2667번: 단지번호붙이기

 

---

풀이

 

 재귀로 구현한 DFS와 큐로 구현한 BFS로 해결할 수 있다. 단지와 집의 수는 mutableList를 이용해 저장해주었다.

 

 주어진 graph를 순회하며 방문한적이 없고 graph가 1인 경우 단지를 추가하고 DFS나 BFS를 호출한다. DFS의 경우에는 graph가 방문하지않고 1인 경우에 다시 DFS함수를 호출해주고, 호출될 때 마다 집의 수를 1 증가시킨다. BFS의 경우에는 해당하는 경우에 Queue에 추가해주고 집의 수를 1 증가시킨다.

 

 리스트를 오름차순으로 정렬하고 리스트의 크기(단지 수)와 내용(집의 수)을 출력하면 된다.

 

---

코드

 

- DFS

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

    val dx = arrayOf(1, 0, -1, 0) // 방향
    val dy = arrayOf(0, 1, 0, -1)

    val num = br.readLine().toInt()
    val graph = Array(num){ IntArray(num) }
    val visited = Array(num){ BooleanArray(num) }
    val ans = mutableListOf<Int>() // 단지와 집의 수를 저장할 리스트

    for(i in 0 until num) {
        val line = br.readLine()
        for(j in 0 until num) {
            graph[i][j] = line[j] - '0'
        }
    }

    fun dfs(x: Int, y: Int) {
        visited[x][y] = true
        ans[ans.size-1]++

        for(i in 0 until 4) {
            val nx = x + dx[i]
            val ny = y + dy[i]

            if(nx < 0 || nx >= num || ny < 0 || ny >= num) continue
            if(visited[nx][ny]) continue

            if(graph[nx][ny] == 1) { // 새로운 집
                dfs(nx, ny)
            }
        }
    }

    for(i in 0 until num) {
        for(j in 0 until num) {
            if(visited[i][j]) continue
            if(graph[i][j] == 1) { // 새로운 단지
                ans.add(0)
                dfs(i,j)
            }
        }
    }

    ans.sort() // 오름차순 정렬

    bw.append("${ans.size}\n")
    ans.forEach {
        bw.append("$it\n")
    }

    bw.write("")
    bw.flush()
    bw.close()
    br.close()
}

 

- BFS

import java.util.*

data class Point(val x: Int, val y: Int)

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

    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)

    val num = br.readLine().toInt()
    val graph = Array(num){ IntArray(num) }
    val visited = Array(num){ BooleanArray(num) }
    val ans = mutableListOf<Int>() // 단지와 집의 수를 저장할 리스트

    for(i in 0 until num) {
        val line = br.readLine()
        for(j in 0 until num) {
            graph[i][j] = line[j] - '0'
        }
    }

    fun bfs(x: Int, y: Int) {
        val queue : Queue<Point> = LinkedList()
        visited[x][y] = true
        ans[ans.size-1]++
        queue.add(Point(x, y))

        while (queue.isNotEmpty()) {
            val cur = queue.poll()

            for(i in 0 until 4) {
                val nx = cur.x + dx[i]
                val ny = cur.y + dy[i]

                if(nx < 0 || nx >= num || ny < 0 || ny >= num) continue
                if(visited[nx][ny]) continue

                if(graph[nx][ny] == 1) { // 새로운 집
                    visited[nx][ny] = true
                    ans[ans.size-1]++
                    queue.add(Point(nx, ny))
                }
            }
        }
    }

    for(i in 0 until num) {
        for(j in 0 until num) {
            if(visited[i][j]) continue
            if(graph[i][j] == 1) { // 새로운 단지
                ans.add(0)
                bfs(i,j)
            }
        }
    }

    ans.sort() // 오름차순으로 정렬

    bw.append("${ans.size}\n")
    ans.forEach {
        bw.append("$it\n")
    }

    bw.write("")
    bw.flush()
    bw.close()
    br.close()
}