[백준] 섬의 개수 (4963)(Kotlin)

원본 문제 : https://www.acmicpc.net/problem/4963

 

<첫번째>DFS

import java.io.*
import java.util.*

var x = 0
var y = 0
val dx: IntArray = intArrayOf(-1,1,0,0,-1,1,-1,1)
val dy: IntArray = intArrayOf(0,0,-1,1,-1,-1,1,1)
var count = 0
var map: Array<IntArray> = arrayOf()
var visited: Array<BooleanArray> = arrayOf()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    var str = readLine().split(" ")
    x = str[0].toInt()
    y = str[1].toInt()


    while ( x != 0 && y != 0 ) {

        count = 0

        map = Array(y) { IntArray(x) }
        visited = Array(y) { BooleanArray(x) }

        for ( i in 0 until y ) {
            for ( j in 0 until x ) {
                visited[i][j] = false
            }
        }

        for ( i in 0 until y ) {
            val str = readLine().split(" ")
            for ( j in 0 until x ) {
                map[i][j] = (str[j]+"").toInt()
            }
        }

        for ( i in 0 until y ) {
            for ( j in 0 until x ) {
                if ( !visited[i][j] && map[i][j] == 1 ) {
                    count += 1
                    dfs(i, j)
                }
            }
        }

        println(count)

        str = readLine().split(" ")
        x = str[0].toInt()
        y = str[1].toInt()


    }

}

fun dfs(yy: Int, xx: Int) {

    visited[yy][xx] = true

    for ( i in 0 until 8 ) {
        val nx = xx + dx[i]
        val ny = yy + dy[i]

        if ( nx < 0 || ny < 0 || nx >= x || ny >= y )
            continue

        if ( !visited[ny][nx] && map[ny][nx] == 1 ) {
            dfs(ny, nx)
        }
    }


}

 

<두번째>BFS(실패-메모리초과)

import java.io.*
import java.util.*

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

var x = 0
var y = 0
val dx: IntArray = intArrayOf(-1,1,0,0,-1,1,-1,1)
val dy: IntArray = intArrayOf(0,0,-1,1,-1,-1,1,1)
var count = 0
var map: Array<IntArray> = arrayOf()
var visited: Array<BooleanArray> = arrayOf()
var queue: Queue<Dot> = LinkedList<Dot>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {


    var str = readLine().split(" ")
    x = str[0].toInt()
    y = str[1].toInt()


    while ( x != 0 && y != 0 ) {

        count = 0

        map = Array(y) { IntArray(x) }
        visited = Array(y) { BooleanArray(x) }

        for ( i in 0 until y ) {
            for ( j in 0 until x ) {
                visited[i][j] = false
            }
        }

        for ( i in 0 until y ) {
            val str = readLine().split(" ")
            for ( j in 0 until x ) {
                map[i][j] = (str[j]+"").toInt()
            }
        }

        for ( i in 0 until y ) {
            for ( j in 0 until  x ) {
                if ( !visited[i][j] && map[i][j] == 1 ){
                    queue.add(Dot(i, j))
                    count += 1
                    bfs()
                }
            }
        }

        println(count)

        str = readLine().split(" ")
        x = str[0].toInt()
        y = str[1].toInt()


    }

}

fun bfs() {

    while ( !queue.isEmpty() ) {
        val d = queue.poll()

        visited[d.y][d.x] = true

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

            if (nx < 0 || ny < 0 || nx >= x || ny >= y)
                continue

            if (!visited[ny][nx] && map[ny][nx] == 1) {
                queue.add(Dot(ny, nx))
            }
        }
    }

}