Custom Grid - boostcampwm2025/and01-boostcamp GitHub Wiki

문제

Compose 라이브러리에서 제공하는 Layout이 UI 요구사항을 만족시킬 수 없음.

1. 알고리즘 개요

1.1 2D Occupied Grid 방식

• rows × columns 크기의 2차원 Boolean 배열을 사용
• 각 아이템 배치 시, 해당 아이템이 차지할 모든 셀을 순회하며 충돌 여부 검사
• 빈칸이 존재하는 임의 위치 배치 허용

주요 코드

// 그리드 점유 상태
val occupied = Array(rows) { BooleanArray(columns) }

// 특정 위치에 아이템 배치 가능 여부 검사
fun canPlace(r: Int, c: Int, rs: Int, cs: Int): Boolean {
    if (r + rs > rows || c + cs > columns) return false

    for (rr in r until r + rs) {
        for (cc in c until c + cs) {
            if (occupied[rr][cc]) return false
        }
    }
    return true
}

// 아이템 배치 후 점유 상태 마킹
fun mark(r: Int, c: Int, rs: Int, cs: Int) {
    for (rr in r until r + rs) {
        for (cc in c until c + cs) {
            occupied[rr][cc] = true
        }
    }
}

// 아이템 배치 로직
for (r in 0 until rows) {
    for (c in 0 until columns) {
        if (canPlace(r, c, item.rowSpan, item.colSpan)) {
            mark(r, c, item.rowSpan, item.colSpan)
            // placeable 배치 처리
            break
        }
    }
}

---

1.2 축(열) 쌓기 방식 (Skyline / Column Height)

• 각 열(column)에 대해 현재까지 쌓인 높이만 관리
• 아이템은 항상 아래에서 위로만 쌓임
• 중간 빈칸(holes)이 존재하지 않는 구조를 전제로 함

주요 코드

// 각 열의 현재 높이
val columnHeights = IntArray(columns) { 0 }

// 아이템 배치 로직
for (c in 0..columns - item.colSpan) {

    // 해당 아이템이 차지할 열 범위 중 가장 높은 높이
    val baseRow = (c until c + item.colSpan)
        .maxOf { columnHeights[it] }

    // 그리드 높이 초과 시 배치 불가
    if (baseRow + item.rowSpan > rows) continue

    // 배치 확정 후 열 높이 갱신
    for (cc in c until c + item.colSpan) {
        columnHeights[cc] = baseRow + item.rowSpan
    }

    // placeable 배치 처리
    break
}

축 쌓기 방식 알고리즘 수정

var bestCol = -1
var bestBaseRow = Int.MAX_VALUE

for (c in 0..columns - item.colSpan) {
    val baseRow = (c until c + item.colSpan).maxOf { columnHeights[it] }
    if (baseRow + item.rowSpan > rows) continue

    if (baseRow < bestBaseRow) {
        bestBaseRow = baseRow
        bestCol = c
    }
}

가장 낮은 최적의 열을 찾는 방식으로 수정

---

2. 배치 판단 로직 비교

2.1 2D Occupied Grid 방식

1. 모든 (row, column) 위치를 순회
2. 아이템이 차지할 rowSpan × colSpan 영역 전체 검사
3. 하나라도 이미 occupied 상태면 배치 불가
4. 배치 가능 시 해당 영역 전체를 occupied로 마킹

블록 하나 당 시간 복잡도: O(rows × columns × rowSpan × colSpan)

장점

• 중간 빈칸 활용 가능
• 비교적 아이템 순서 의존성이 낮음(빈 공간이 생기는 아이템 순서더라도 모든 아이템이 배치 됨)

단점

• 로직 복잡도 높음
• 시간 복잡도가 비교적 높음

---

2.2 축 쌓기 방식

1. 배치 시작 열 c만 순회
2. c .. c + colSpan 범위에서 최대 columnHeight 계산
3. baseHeight + rowSpan <= rows 인지만 검사
4. 배치 확정 시 해당 열들의 height 갱신

블록 하나 당 시간 복잡도: O(columns × colSpan)

장점

• 비교적 시간 복잡도가 낮음

단점

• 중간 빈칸 활용 불가
• 아이템 순서에 따른 결과 의존성 큼(빈 공간이 생기는 순서일 경우 모든 아이템을 배치하지 못함)

---

3. 결론

• 2D Occupied Grid 방식은 높은 자유도와 정밀 제어를 제공한다.
• 축 쌓기 방식은 단순함과 성능을 제공하는 대신 제약을 수용해야 한다.
• 현재는 배치와 순서를 보장해주기 때문에 시간복잡도가 낮은 축 쌓기 방식을 선택

4. 추가 고려

• 그리드 뷰에 단순 이미지 컨텐츠만을 고정적으로 사용가능 하나 추후 다른 컨텐츠도 삽입 가능하게 확장

• 현재는 고정된 배치, 순서로 블럭들을 배치하고 있으나 추후 사용자의 편의성을 고려해야함

  • 그리드의 행과 열을 자유롭게 변경 가능
  • 그리드 내의 블록들의 배치를 변경
  • 그리드 내 블록을 추가하거나 블록의 크기를 변경

• 이미지를 블럭에 배치 후 crop으로 처리 중이기에 이미지의 비율을 고려하지 못한 채 잘려서 보일 가능성이 존재

  • 내부 컨텐츠 크기를 고려해 적절한 블록에 배치하는 처리