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

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

1012번: 유기농 배추

 

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

 

 

1. 설명

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

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

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

 

2. 소스코드

      

      

      

    
    

      <kotlin />
    
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
}

 

3. 후기

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