[백준] 1012 (유기농 배추)

#1 알고리즘

먼저, 모든 배추에 번호 0을 부여한다. 그리고 배추들을 순회하며 해당 배추의 번호가 0이면 1부터 시작하는 번호를 부여한다. 번호가 부여된 배추는 자신을 기준으로 동, 서, 남, 북에 있는 번호가 0인 배추에 같은 번호를 전달한다. 그리고 전달된 배추 또한 재귀적으로 동, 서, 남, 북에 같은 번호를 전달한다. 같은 번호가 부여된 배추를 하나의 '배추 그룹'으로 생각한다. 여러 개의 '배추 그룹'에 부여된 번호 중 가장 큰 것을 출력하면 그것이 곧 지렁이의 최소 마릿수다. 

 

#2 코드 - 코틀린

/* count = 갯수
 * number = 번호
 */
lateinit var cabbageMap : HashMap<Pair<Int, Int>, Int>

fun main() {
    val testCaseCount = readln().toInt()
    for(i : Int in 0..<testCaseCount) {
        val fieldInformations = readln().split(" ")
        // val fieldWidthLength = fieldInformations[0].toInt()
        // val fieldHeightLength = fieldInformations[1].toInt()
        val cabbageCount = fieldInformations[2].toInt()

        cabbageMap = HashMap()
        for(j : Int in 0..<cabbageCount) {
            val cabbageSiteArray = readln().split(" ")
            val cabbageSite = Pair(cabbageSiteArray[0].toInt(), cabbageSiteArray[1].toInt())
            cabbageMap[cabbageSite] = 0
        }

        println(calculateMinCountOfEarthworm())
    }
}

/* 아직 지렁이가 없고, 배추만 덩그러니 있다면 있다면 cabbageMap의 Value는 0
 * 1번 지렁이의 영역(cabbageGroup)에 해당하는 Key(배추의 위치)면 Value는 1
 * 2번 지렁이의 영역(cabbageGroup)에 해당하는 Key(배추의 위치)면 Value는 2
 * 3번 지렁이의 영역(cabbageGroup)에 해당하는 Key(배추의 위치)면 Value는 3
 * ...
 */
fun calculateMinCountOfEarthworm(): Int {
    var cabbageGroupNumber = 1
    for((key, value) in cabbageMap) {
        if(value == 0) { 
            cabbageGroupNumbering(key, cabbageGroupNumber)
            cabbageGroupNumber++
        }
        // value가 null(= 해당 자리에 배추가 없음)이거나, 0이 아닌 숫자(= 이미 다른 배추 그룹에 속함)면 continue
    }

    return cabbageGroupNumber - 1
}

fun cabbageGroupNumbering(cabbageSite : Pair<Int, Int>, cabbageGroupNumber : Int) {
    if(cabbageMap[cabbageSite] == 0) {
        cabbageMap[cabbageSite] = cabbageGroupNumber

        cabbageGroupNumbering(Pair(cabbageSite.first + 1, cabbageSite.second), cabbageGroupNumber) // 동
        cabbageGroupNumbering(Pair(cabbageSite.first - 1, cabbageSite.second), cabbageGroupNumber) // 서
        cabbageGroupNumbering(Pair(cabbageSite.first, cabbageSite.second - 1), cabbageGroupNumber) // 남
        cabbageGroupNumbering(Pair(cabbageSite.first, cabbageSite.second + 1), cabbageGroupNumber) // 북

    // cabbageMap[cabbageSite]이 null(= 해당 자리에 배추가 없음)이거나, 0이 아닌 숫자(= 이미 다른 배추 그룹에 속함)면 return
    } else {
        return
    }
}