백준 4963번 - 섬의 개수 / Kotlin

1. 문제

4963번: 섬의 개수

가장 기본적인 BFS  문제입니다. 다만 상하좌우 뿐만 아니라 대각선으로도 이동이 가능한 점과 가로 세로의 입력값이 일반적인 경우와 달리 반대로 되어있는 점만 유의하면 어렵지 않았습니다.

2. 알고리즘

1. BFS 방식으로 모든 칸을 검사한다.

2. 상하좌우 뿐만 아니라 대각선으로도 이동이 가능하므로 주의한다.

3. 한번의 BFS 탐색이 끝날때 마다 섬의 개수를 +1 해준다. 

 

3. 코드

/**
 * 2020.08.04
 * DevHyeon
 * BOJ4963 : 섬의 개수
 */
import java.util.*
fun main(){
    val scan = Scanner(System.`in`)

    var testCase = scan.nextLine()
    while(testCase != "0 0"){
        val w: Int // 행의 길이
        val h: Int // 열의 길이
        var answer  = 0

        testCase.split(" ").let {
            w = it[0].toInt()
            h = it[1].toInt()
        }
        var map = Array(h) { IntArray(w) } // 맵
        var check = Array(h){ BooleanArray(w) } // 방문 체크

        /* 배열 입력 받기 */
        for(i in map.indices){
            map[i] = IntArray(w)
            check[i] = BooleanArray(w)
            scan.nextLine().split(" ").let {
                for (j in it.indices) {
                    map[i][j] = it[j].toInt()
                }
            }
        }

        for(i in map.indices){
            for(j in map[i].indices){
                if(!check[i][j] && map[i][j]==1){ // 방문 하지 않았고, 1 이라면 방문
                    check[i][j] = true // 방문 체크
                    bfs(check,map,i,j) // BFS 탐색
                    answer++
                }
            }
        }
        println(answer)
        testCase = scan.nextLine()
    }
}

fun bfs(check: Array<BooleanArray>, map: Array<IntArray>, i: Int, j:Int) {
    val di = arrayOf(-1,0,1,0,-1,-1,1,1)
    val dj = arrayOf(0,-1,0,1,-1,1,-1,1)
    val q: Queue<Node> = LinkedList()

    q.add(Node(i,j))

    while(!q.isEmpty()){
        q.poll().apply{
            for(i in di.indices){
                val dx = x+di[i]
                val dy = y+dj[i]
                if(dx>=0 && dy>=0 && dx<map.size && dy<map[0].size
                        && !check[dx][dy] && map[dx][dy]==1){ // 상하좌우대각선 모두 검사. 배열의 범위와 방문 기록, 배열요소가 1인지 체크
                    q.offer(Node(dx,dy))
                    check[dx][dy] = true
                }
            }
        }
    }
}

data class Node(val x: Int, var y:Int)

끝.