[백준 1012번] [Kotlin] 유기농 배추

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

1012번: 유기농 배추

 

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

 

 

설명

각각의 점을 정점으로 보고, 인접한 상하좌우의 정점이 서로 연결되어있다고 생각하여,

DFS, BFS로 모든 정점에서 탐색을 수행하며 블럭의 개수를 카운트 할 수 있습니다

DFS, BFS중 어느 것을 사용해도 무방하나, 저는 DFS를 사용해 풀이하였습니다.

 

소스코드

import java.io.BufferedReader
import java.io.InputStreamReader

val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
lateinit var map: Array<Array<Int>>
var n = 0
var m = 0

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

    val T = br.readLine().toInt()

    repeat(T) {
        val mnk = br.readLine().split(" ")
        m = mnk[0].toInt()
        n = mnk[1].toInt()
        val k = mnk[2].toInt()
        var cnt = 0

		// 맵 초기화
        map = Array(n) { Array(m) { 0 } }

        repeat(k) { k ->
            val xy = br.readLine().split(" ")
            map[xy[1].toInt()][xy[0].toInt()] = 1
        }

		// 모든 정점에서 dfs 실행
        repeat(n) { x ->
            repeat(m) { y ->
                if(dfs(x,y)) cnt++
            }
        }

        println(cnt)
    }
}

fun dfs(x: Int, y: Int): Boolean {
    if (map[x][y] == 0) return false

    map[x][y] = 0
    for (i in 0 until 4) {
        val nx = x + dx[i]
        val ny = y + dy[i]

        if (nx !in 0 until n || ny !in 0 until m || map[nx][ny] == 0)
            continue
        dfs(nx, ny)
    }
    return true
}

 

후기

DFS, BFS를 사용한 블럭 개수 카운트의 기초격인 문제였습니다.