[백준] 1012번: 유기농 배추 - Kotlin[코틀린]

문제

 

1012번: 유기농 배추

 

---

풀이

 

 각각의 테스트 케이스마다 입력받은 graph를 DFS, BFS로 탐색한 결과를 출력해주면 된다.

 

 graph는 false로 초기화되어 있는 BooleanArray를 선언한다. 입력받은 좌표는 true로 바꿔준다. for문을 통해 graph의 좌표가 true이면 DFS, BFS 함수를 실행해주고 cnt를 +1 해준다. 이후 cnt를 출력해주면 된다.

 

---

코드

 

- 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 testCase = br.readLine().toInt()

    repeat(testCase) {
        var st = StringTokenizer(br.readLine())
        val (rows, cols, num) = arrayOf(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt())
        val graph = Array(rows){ BooleanArray(cols) }
        var cnt = 0

        repeat(num) {
            st = StringTokenizer(br.readLine())
            graph[st.nextToken().toInt()][st.nextToken().toInt()] = true
        }

        fun bfs(x: Int, y: Int) {
            val queue : Queue<Point> = LinkedList()
            queue.add(Point(x, y))
            graph[x][y] = false

            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 >= rows || ny < 0 || ny >= cols) continue

                    if(graph[nx][ny]) {
                        graph[nx][ny] = false
                        queue.add(Point(nx, ny))
                    }
                }
            }
        }

        for(i in 0 until rows) {
            for(j in 0 until cols) {
                if(graph[i][j]) {
                    cnt++
                    bfs(i, j)
                }
            }
        }

        bw.append("$cnt\n")
    }

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

 

- DFS

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 testCase = br.readLine().toInt()

    repeat(testCase) {
        var st = StringTokenizer(br.readLine())
        val (rows, cols, num) = arrayOf(st.nextToken().toInt(), st.nextToken().toInt(), st.nextToken().toInt())
        val graph = Array(rows){ BooleanArray(cols) }
        var cnt = 0

        repeat(num) {
            st = StringTokenizer(br.readLine())
            graph[st.nextToken().toInt()][st.nextToken().toInt()] = true
        }

        fun dfs(x: Int, y: Int) {
            graph[x][y] = false

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

                if(nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue

                if(graph[nx][ny]) {
                    dfs(nx, ny)
                }
            }
        }

        for(i in 0 until rows) {
            for(j in 0 until cols) {
                if(graph[i][j]) {
                    cnt++
                    dfs(i, j)
                }
            }
        }

        bw.append("$cnt\n")
    }

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