2020-08-30

모든 조합의 가짓수 구하기

보통 게임에서는 모자, 갑옷, 장갑, 신발, 액세서리 등으로 부위를 세분화 해놓는다. 모자만 쓰는 경우도 있고, 갑옷만 입는 경우도 있는데 모든 조합의 가짓수는 어떻게 구할까?written by

게임에서 부위 별로 아이템을 장착한다고 가정하자

보통 게임에서는 모자, 갑옷, 장갑, 신발, 액세서리 등으로 부위를 세분화 해놓는다.
모자만 쓰는 경우도 있고, 갑옷만 입는 경우도 있는데 모든 조합의 가짓수는 어떻게 구할까?

하나의 예시를 들어보자.

머리에 쓰는 아이템으로 모자, 머리띠, 담배가 있고 몸통에 입는 아이템으로 갑옷이 있다면 다음과 같이 7개의 조합이 나온다.

  • 모자
  • 머리띠
  • 담배
  • 갑옷
  • 모자, 갑옷
  • 머리띠, 갑옷
  • 담배, 갑옷

Algorithm

기본 원리는 각각의 부위로 그룹을 나누고 이것을 조합하는 모든 경우의 수를 구하는 것이다.

모든 부위에 대한 서브셋을 구한다고 생각하면 편한데 단지 각 서브셋에 해당하는 아이템 개수에 따라 조합이 여러 개 생기는 것이다.

이는 다음과 같이 접근할 수 있다.

모든 부위를 배열에 담으면 [머리(3개), 몸통(1개)]처럼 표현이 가능하다.
이제 해당 부위를 입는 경우는 1로 표현하고, 입지 않는 경우는 0으로 표현하면

  • 머리에 쓰는 아이템만 있는 경우는 [1, 0], 머리에 아이템이 3개이므로 3가지
  • 몸통에 입는 아이템만 있는 경우 [0, 1], 몸통에 아이템이 1개이므로 1가지
  • 둘 다 쓰는 경우 [1, 1], 머리에 아이템이 3개이고 몸통에 1가지이므로 3가지

이를 전부 더하면 위에서 말한 7가지가 나온다.

Kotlin Code

이제 이를 코드로 구현해보자. 나는 코틀린을 주로 사용하기 때문에 코틀린으로 구현했다.

// pow 함수를 쓰기 위해서 import
import kotlin.math.pow

// 모자, 머리띠, 담배를 머리 카테고리에 담고, 갑옷을 몸통 카테고리에 담아서 아이템 리스트를 생성
val itemList =
    listOf(
        listOf("hat", "head"),
        listOf("hair_band", "head"),
        listOf("cigarette", "head"),
        listOf("armor", "body")
    )

// 모든 조합의 가짓수를 출력
println(getAllCategoryItemCombinationCount(itemList))

// 아이템 리스트에서 해당 카테고리에 속하는 아이템의 개수를 반환하는 함수
fun getCategoryCount(itemList: List<List<String>>, category: String) =
    itemList.filter { item -> item.contains(category) }.size

// 아이템 리스트에서 각각의 카테고리에 해당하는 아이템의 개수들을 배열로 만들어서 반환하는 함수
fun makeCategoryItemNumberList(itemList: List<List<String>>): List<Int> {
    val categoryItemNumberList = mutableListOf<Int>()
    val categoryList = mutableListOf<String>()

    itemList.forEach { item ->
        val category = item[1]

        when {
            !categoryList.contains(category) -> {
                categoryList.add(category)
                categoryItemNumberList.add(getCategoryCount(itemList, category))
            }
        }
    }

    return categoryItemNumberList
}

// 아이템 리스트로부터 조합의 개수를 구해서 반환하는 함수
fun getAllCategoryItemCombinationCount(itemList: List<List<String>>): Int {
    var allCombinationCount = 0
    val categoryItemNumberList = makeCategoryItemNumberList(itemList)

    // i는 각 서브셋을 의미한다.
    // 2개의 카테고리를 가지는 경우 [0, 1], [1, 0], [1, 1]이라는 서브셋이 존재하게 된다.
    // 1은 이진법으로 01이고, 배열로 나타내면 [0, 1]이다.
    // 2는 이진법으로 10이고, 배열로 나타내면 [1, 0]이다.
    // 3은 이진법으로 11이고, 배열로 나타내면 [1, 1]이다.
    // 이런 식으로 모든 서브셋에 대하여 접근한다.
    // 이진법의 모든 가짓수를 구하는 방법은 2를 카테고리 개수만큼 승수해주면 된다.
    for (i in 1 until (2.0.pow(categoryItemNumberList.size)).toInt()) {

        // shift 연산을 위해 i를 j에 저장하고, 배열에 접근하기 위해서 k라는 변수를 사용한다.
        var j = i
        var k = 0

        // 각 서브셋의 조합의 수를 카운트하는 변수
        var combinationCount = 0

        // 어떤 숫자를 1과 and 연산하면 이진법으로 표현된 마지막 숫자가 1인지 아닌지 판별할 수 있다.
        // 예를 들어, 이진수 11을 1과 and 연산하면 true, 이진수 00을 1과 and 연산하면 false.
        // 이 원리를 이용해서 각 부위에 접근한다.
        // j가 0이 되면 남은 부위가 없다는 의미이므로 루프문을 벗어난다.
        while (j != 0) {

            // 해당 서브셋에 속하는 부위일 경우를 의미한다.
            if (j and 1 == 1) {

                // 2개 이상의 부위가 조합되는 경우는 곱하기를 하고,
                // 1개의 부위는 곱하기가 불가능하므로 더해준다.
                if (combinationCount != 0) {
                    combinationCount *= categoryItemNumberList[k]
                } else {
                    combinationCount += categoryItemNumberList[k]
                }
            }

            // 이제 j를 right shift 연산하면 다음 부위에 접근할 수 있다.
            j = j shr 1

            // 다음 부위로 접근하기 위해 k도 1씩 증가시킨다.
            k += 1
        }

        // 각 서브셋에 대한 조합의 수를 더해준다.
        allCombinationCount += combinationCount
    }

    return allCombinationCount
}
2020 © Cinntiq's Studio