[백준 3184번] [Kotlin] 양

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

3184번: 양

 

난이도 : 실버 1
태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

설명

울타리로 분리된 각 구역에 양과 늑대가 있습니다.

양이 더 많다면 늑대를 쫒아낼 수 있고

늑대가 더 많거나 양과 수가 동일하다면 늑대가 양을 다 먹어버립니다.

 

DFS, BFS를 사용한 그룹화 기법을 응용하는 문제입니다.

 

 

 

접근방법

1. 한 점을 대상으로 방문하지 않은 점이라면 해당 점을 DFS/BFS 탐색한다.

2. 상하좌우로 인접한 칸들을 연속으로 탐색하며, 양과 늑대의 개수를 카운팅한다.

3. DFS/BFS가 종료된 시점에 양의 수가 더 많다면 양의 개수를 누적하여 더하고,

같거나 늑대의 수가 더 많다면 늑대의 개수를 누적하여 더한다.

4. 탐색하지 않은 다른 정점에 대해 DFS/BFS 탐색을 수행한다.

 

 

 

소스코드

lateinit var visited: Array<BooleanArray>
lateinit var map: Array<CharArray>
var dx = intArrayOf(0, 0, -1, 1)
var dy = intArrayOf(-1, 1, 0, 0)
var wolfCount = 0
var sheepCount = 0
var n = 0
var m = 0

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    map = Array(n) { readLine().toCharArray() }
    visited = Array(n) { BooleanArray(m) }

    var ansWolfCount = 0
    var ansSheepCount = 0

    for (i in 0..<n) {
        for (j in 0..<m) {
            wolfCount = 0
            sheepCount = 0
            dfs(i, j)

            if (wolfCount >= sheepCount) {
                ansWolfCount += wolfCount
            } else {
                ansSheepCount += sheepCount
            }
        }
    }

    println("$ansSheepCount $ansWolfCount")
}

fun dfs(x: Int, y: Int) {
    if (x !in 0..<n || y !in 0..<m || visited[x][y]) return

    when (map[x][y]) {
        'v' -> wolfCount++
        'o' -> sheepCount++
        '#' -> return
    }

    visited[x][y] = true

    for (i in 0..<4) {
        dfs(x + dx[i], y + dy[i])
    }
}

 

 

 

 

후기

DFS는 언제해도 재밌습니다.