2020-08-31

모든 조합 구하기

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

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

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

하나의 예시를 들어보자.

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

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

Algorithm

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

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

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

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

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

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

Kotlin Code

import kotlin.math.pow

// 아이템 카테고리를 Enum Class 지정.
enum class Category { HEAD, BODY, ACCESSORY }

// 아이템 카테고리를 키값으로 가지는 아이템 리스트 해시 맵.
val items = hashMapOf(
    Pair(Category.HEAD, mutableListOf("cigarette", "hair_band", "hat")),
    Pair(Category.BODY, mutableListOf("armor")),
    Pair(Category.ACCESSORY, mutableListOf("amulet", "ring"))
)

// 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(items.size)).toInt()) {

    // shift 연산을 위해 i를 j에 저장하고, 배열에 접근하기 위해서 k라는 변수를 사용한다.
    val itemCollections = mutableListOf<MutableList<String>>()
    var j = i
    var k = 0

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

    printItemCombinations(null, 0, itemCollections)
}

// items 값에 이전 카테고리의 모든 아이템을 합쳐서 저장하고, index 값을 증가시키면서 printItemCombinations 재귀적 호출.
fun printItemCombinations(items: String?, index: Int, itemCollections: MutableList<MutableList<String>>) {
    return if (index >= itemCollections.size) {
        println(items?.split(","))
    } else {
        itemCollections[index].forEach { item ->
            printItemCombinations(items?.let { "$items,$item" } ?: item, index + 1, itemCollections)
        }
    }
}

Result

[cigarette]
[hair_band]
[hat]
[armor]
[cigarette, armor]
[hair_band, armor]
[hat, armor]
[amulet]
[ring]
[cigarette, amulet]
[cigarette, ring]
[hair_band, amulet]
[hair_band, ring]
[hat, amulet]
[hat, ring]
[armor, amulet]
[armor, ring]
[cigarette, armor, amulet]
[cigarette, armor, ring]
[hair_band, armor, amulet]
[hair_band, armor, ring]
[hat, armor, amulet]
[hat, armor, ring]
2021 © Cinntiq's Studio