[종만북] 문제: BOARDCOVER2

게시 2025/01/16 업데이트 2025/03/06

By 정승우

10 분읽는 시간

문제

게임판과 블록의 모양이 주어집니다. 게임판의 크기와 블록의 크기는 최대 10x10입니다.

게임판에 놓을 수 있는 최대의 블록 수를 구하시오.

문제 링크

서론

가지치기 기법을 이용해서 탐색의 수를 줄여봅시다.

가지치기

가지치기 기법은 탐색 과정에서 최적해로 연결될 가능성이 없는 부분들을 잘라냅니다.

현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 구한 최적해보다 나쁘면 탐색을 종료할 수 있다는 점입니다.

그러면 지금까지 구한 최적해가 진짜 최적해랑 비슷할 수록, 탐색을 덜 할수 있겠죠.

그래서, 최적해에 근접한 값을 구하기 위해서 휴리스틱을 이용합니다.

휴리스틱은 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 빠른 의사결정을 할 수 있도록 고안된 컴퓨터 알고리즘입니다.

보통 문제의 조건을 변형해서 최적해보다 의도적으로 덜 최적화시켜 최적해 값으로 쓸 적당한 값을 찾습니다. 이를 낙관적인 휴리스틱이라고 합니다.

알고리즘 구상

지금까지 어려운 알고리즘 문제들을 풀어봤지만, 알고리즘의 구현이 어려웠지 구상 자체는 할 만 했으나, 이 문제는 구상 자체도 매우 어려웠습니다.

알고리즘 설계

$block$의 $0°, 90°, 180°, 270°$를 미리 구해놓습니다. 가장 위쪽의 왼쪽 블록이 $(0,0)$ 좌표라고 생각하면, 나머지 연결된 블록들을 상대 좌표로 표현합니다. 이를 통해 중복되는 블록(회전해도 같은 모양)을 지울 수 있습니다.
알고리즘을 구현하기 위해 연산에 필요한 추가적인 값을 구합니다.
- 비어 있는 칸 covered[i][j] == 0의 위치를 vector<pair<int,int>> emptyCells에 저장합니다.
- 전체 빈 칸의 개수를 int leftCells 변수에 저장하여 가지치기 조건에 활용합니다.
$Backtracking$을 통해 블록 배치를 시도합니다. 재귀함수 $Backtrack(index, placed, leftCells, emptyCells)$를 이용합니다.
재귀함수 $Backtrack$에 가지치기를 적용합니다.
- 현재까지 배치한 블록 수: $placed$, 남은 빈 칸 수 $leftCells$, 한 블록의 칸 개수 $blockSize$로 정의합니다.
- $placed + \frac{leftCells}{blockSize} \leq best$일 경우, 더 이상 최적해를 찾을 가능성이 없으므로 재귀 호출을 종료합니다.
최적 배치 수를 갱신합니다. $best = max(best, placed)$
최종적으로 $best$를 출력합니다.

정도로 구상할 수 있습니다.

알고리즘 구현

블록의 회전 구현

블록의 $90°$회전을 구현하는 함수를 작성합니다.

  
vector<string> rotateBlock(const vector<string> &arr) {
    vector<string> ret(arr[0].size(), string(arr.size(), ' '));
    for (int i = 0; i < (int)arr.size(); i++) {
        for (int j = 0; j < (int)arr[0].size(); j++) {
            ret[j][arr.size() - i - 1] = arr[i][j];
        }
    }
    return ret;
}

블록의 모든 형태 생성

앞서 만든 rotateBlock()을 이용하여 블록의 형태를 생성하는 함수를 만듭니다.

이후 주어지는 게임판의 2차원 index로 접근하기 때문에, 블록의 특정 칸을 $(0,0)$좌표로 잡고, 나머지 칸의 좌표를 상대적인 좌표로 표현합니다. 이를 vector<pair<int, int>>로 저장합니다.

$(0,0)$은 블록의 채워진 칸이 존재하는 첫 번째 줄, 제일 왼쪽 칸입니다. 이 점에 유의하세요.

  
void generateRotations(vector<string> block) {
    rotations.clear();
    rotations.resize(0);
    for (int index = 0; index < 4; index++) {
        vector<pair<int, int>> coords;
        int originY = -1, originX = -1;
        for (int i = 0; i < (int)block.size(); i++) {
            for (int j = 0; j < (int)block[i].size(); j++) {
                if (block[i][j] == '#') {
                    if (originY == -1) {
                        originY = i;
                        originX = j;
                    }
                    coords.push_back({i - originY, j - originX});
                }
            }
        }
        sort(coords.begin(), coords.end());
        rotations.push_back(coords);
        block = rotateBlock(block);
    }
    sort(rotations.begin(), rotations.end());
    rotations.erase(unique(rotations.begin(), rotations.end()),
                    rotations.end());
    blockSize = (int)rotations[0].size();
}

Block을 추가, 제거를 도와주는 helper함수

helper함수를 작성합니다. 유의할 점은, 수행할 수 없으면 false를 리턴하고, 수행할 수 있으면 수행 이후 true를 리턴합니다.

  
bool setBlock(int y, int x, const vector<pair<int, int>> &shape, int delta) {
    // delta == 1: 놓기 시도, delta == -1: 되돌리기
    bool canPlace = true;
    for (auto &cell : shape) {
        int ny = y + cell.first;
        int nx = x + cell.second;
        if (ny < 0 || ny >= boardH || nx < 0 || nx >= boardW) {
            canPlace = false;
        } else {
            if (delta == 1 && covered[ny][nx] != 0) {
                canPlace = false;
            }
        }
    }
    if (canPlace) {
        for (auto &cell : shape) {
            int ny = y + cell.first;
            int nx = x + cell.second;
            covered[ny][nx] += delta;
        }
    }
    return canPlace;
}

Backtrack

앞서 작성한 setBlock()을 이용하여 backtrack를 구현합니다.

함수의 작동 순서는 다음과 같습니다.

함수를 재귀호출하여 빈 칸에 여러가지 블록 배치를 시도합니다. 이후 블록 배치를 다시 지웁니다.
이 칸을 그냥 비워둬야 하는 경우, 이 칸을 고려하지 않기 위해 채우고, 함수를 재귀호출합니다. 이후 다시 비웁니다.
다른 블록에 의해 커버된 칸이거나, emptyCells의 모든 원소를 다 확인했으면 종료합니다.

여기서! 함수의 맨 첫 부분에 가지치기 기법이 들어갑니다.

  
void backtrack(int index, int placed, int leftCells,
               const vector<pair<int, int>> &emptyCells) {
    // 가지치기
    if (placed + leftCells / blockSize <= best) return;

    // 모든 빈 칸을 확인 완료
    if (index == (int)emptyCells.size()) {
        best = max(best, placed);
        return;
    }

    int y = emptyCells[index].first;
    int x = emptyCells[index].second;

    // 이미 커버된 칸이면 넘어간다
    if (covered[y][x] != 0) {
        backtrack(index + 1, placed, leftCells, emptyCells);
        return;
    }

    // 블록 배치 시도
    for (auto &rot : rotations) {
        if (setBlock(y, x, rot, 1)) {
            backtrack(index + 1, placed + 1, leftCells - blockSize, emptyCells);
            setBlock(y, x, rot, -1);
        }
    }

    // 이 칸을 잠그기
    covered[y][x] = 1;
    backtrack(index + 1, placed, leftCells - 1, emptyCells);
    covered[y][x] = 0;
}

Solve

위에 작성된 함수를 이용해 최종적으로 답을 계산하는 함수를 작성합니다.

  
int solveCase() {
    best = 0;
    vector<pair<int, int>> emptyCells;
    int leftCells = 0;

    for (int i = 0; i < boardH; i++) {
        for (int j = 0; j < boardW; j++) {
            covered[i][j] = (board[i][j] == '#');
            if (covered[i][j] == 0) {
                emptyCells.push_back({i, j});
                leftCells++;
            }
        }
    }

    backtrack(0, 0, leftCells, emptyCells);
    return best;
}

최종 코드

여기에서 확인하세요!

알고리즘 개선

남의 코드와 비교

총 실행 시간은 40ms가 나왔으나, 8ms가 나온 코드가 있어서 한번 분석해봤습니다.

차이점은, <bitset>을 이용해 board와 block의 표현을 깔끔하게 했고, (저는 교과서에서 제시하는 vector<string>)으로 풀었습니다.

그리고, 메모이제이션을 <unordered_map>을 이용해 구현하여 차이가 났습니다.

전체 코드는 여기에서 확인할 수 있습니다.

알고리즘, 종만북

알고리즘 종만북