[백준] 3184번: 양 - Kotlin[코틀린]

문제

 

3184번: 양

 

 

---

풀이

 

 큐를 이용한 너비 우선 탐색(BFS)으로 해결하였다. 반복문을 통해 울타리가 아닌 경우에 BFS 탐색을 수행하고 방문을 처리 해준다.

 

 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 (rows, cols) = br.readLine().split(' ').map { it.toInt() }
    val map = Array(rows){ br.readLine() }
    val visited = Array(rows){ BooleanArray(cols) }
    val dx = arrayOf(1, 0, -1, 0)
    val dy = arrayOf(0, 1, 0, -1)

    var sheep = 0 // 살아있는 양
    var wolf = 0 // 살아있는 늑대

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

        var wCnt = 0
        var sCnt = 0

        if(map[x][y] == 'o') {
            sCnt++
        }
        if(map[x][y] == 'v') {
            wCnt++
        }

        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(visited[nx][ny]) continue
                if(map[nx][ny] == '#') continue // 울타리인 경우 넘어감
                visited[nx][ny] = true

                if(map[nx][ny] == 'o') {
                    sCnt++
                }
                if(map[nx][ny] == 'v') {
                    wCnt++
                }
                queue.add(Point(nx, ny))
            }
        }

        if(sCnt > wCnt) { // 살아있는 양과 늑대의 수 계산
            sheep += sCnt
        } else {
            wolf += wCnt
        }
    }

    for(i in 0 until rows) {
        for(j in 0 until cols) {
            if(map[i][j] != '#' && !visited[i][j]) {
                bfs(i, j)
            }
        }
    }

    bw.write("$sheep $wolf")
    bw.flush()
    bw.close()
    br.close()
}