백준 - 11123 양 한마리... 양 두마리... (코틀린)

[문제]

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

11123번: 양 한마리... 양 두마리...

[풀이]

전형적인 bfs 문제이다. 서로 다른 연결성분의 개수를 찾는 문제로 각 좌표를 돌면서 방문하지 않은 양의 좌표일 때 1씩 카운트해주고 bfs를 돌면서 같은 연결성분의 양은 방문하면 쉽게 답을 찾을 수 있다.

[코드]

import java.lang.StringBuilder
import java.util.*

private var t = 0
private var h = 0
private var w = 0
private lateinit var sheep : Array<CharArray>
private lateinit var visited : Array<BooleanArray>
private var answer = 0
private val dx = listOf(1,-1,0,0)
private val dy = listOf(0,0,1,-1)
private val sb = StringBuilder()
fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    t = br.readLine().toInt()
    repeat(t){ _ ->
        br.readLine().split(" ").map { it.toInt() }.apply {
            h = this[0]
            w = this[1]
        }
        answer = 0
        sheep = Array(h){ CharArray(w) }
        visited =  Array(h){ BooleanArray(w) }
        repeat(h){
            sheep[it] = br.readLine().toCharArray()
        }
        for(i in 0 until h){
            for(j in 0 until w){
                if(sheep[i][j] == '#' && !visited[i][j])
                    bfs(i,j)
            }
        }
        sb.append(answer).append("\n")

    }
    bw.write(sb.toString())
    bw.flush()
    bw.close()
}
private fun bfs(px : Int, py : Int){
    val queue : Queue<Pair<Int,Int>> = ArrayDeque()
    queue.add(Pair(px,py))
    answer += 1
    visited[px][py] = true
    while(queue.isNotEmpty()){
        val (x, y) = queue.poll()
        for(i in 0 .. 3){
            val nx = x + dx[i]
            val ny = y + dy[i]
            if(nx < 0 || ny <0 || nx >= h || ny >= w) continue
            if(sheep[nx][ny]=='.') continue
            if(visited[nx][ny]) continue
            queue.add(Pair(nx,ny))
            visited[nx][ny] = true
        }
    }
}