[프로그래머스/C++] 퍼즐 조각 채우기

https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

문제 분석: 퍼즐 맞추기 문제

이 문제는 게임 보드의 빈 공간에 테이블 위의 퍼즐 조각을 규칙에 맞게 최대한 많이 채우는 문제입니다. 주어진 퍼즐 조각을 회전시켜 빈칸에 맞추되, 인접한 칸이 비어 있지 않아야 하며, 퍼즐 조각은 한 번에 하나씩만 채울 수 있습니다. 퍼즐 조각의 뒤집기는 허용되지 않습니다. 게임 보드와 퍼즐 테이블은 각각 1x1 크기의 정사각형 격자 모양입니다. 목표는 퍼즐 조각을 적절히 배치해 최대한 많은 칸을 채우는 것입니다.

제한 사항

• 게임 보드와 퍼즐 테이블은 정사각형이며, 크기는 최소 3x3, 최대 50x50입니다.
• 퍼즐 조각은 최소 1개에서 최대 6개까지 연결된 1x1 정사각형으로 이루어져 있습니다.
• 퍼즐 조각을 회전시킬 수 있지만, 뒤집을 수는 없습니다.

문제 풀이 접근법

1. 퍼즐 조각 추출: 먼저 테이블 위의 퍼즐 조각을 추출합니다. bfs를 사용하여 퍼즐 조각의 모양을 추출하고, 이 모양을 회전할 수 있는 모든 경우의 수를 저장합니다.
2. 게임 보드의 빈칸 추출: 같은 방식으로 게임 보드에서 비어 있는 공간의 모양을 추출합니다.
3. 퍼즐 조각 회전 및 매칭: 추출한 퍼즐 조각을 회전시켜 게임 보드의 빈칸과 매칭합니다. 퍼즐 조각을 회전한 4가지 경우 중 하나가 빈칸의 모양과 일치하는지 확인합니다. 일치하면 해당 빈칸을 퍼즐 조각으로 채웁니다.
4. 중복 체크 및 최댓값 계산: 퍼즐 조각을 한번 사용하면 다시 사용할 수 없으므로 중복 사용을 방지하고, 채운 퍼즐 칸 수를 누적해 최종 결과를 도출합니다.

코드 분석

퍼즐 조각 회전 함수

vector<vector<vector<int>>> rotate(vector<vector<int>> s){
    vector<vector<vector<int>>> ans;
    int n = s.size();
    int m = s[0].size();
    ans.push_back(s);

    for(int k = 0; k < 3; k++) {
        vector<vector<int>> ret(m, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                ret[j][n - i - 1] = s[i][j];
            }
        }
        s = ret;
        ans.push_back(ret);
        swap(n,m);
    }

    return ans;
}

이 함수는 주어진 퍼즐 조각을 90도씩 회전시켜 4가지 경우의 수를 반환합니다.

BFS를 통한 퍼즐 조각 추출

vector<vector<int>> bfsShape(vector<vector<int>>& table, int x, int y ,int num, vector<vector<bool>>& vis){
    queue<pair<int,int>> q;
    q.push({x,y});
    int minX = x;
    int maxX = x;
    int minY = y;
    int maxY = y;
    vis[x][y] = true;

    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i<4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if(nx >= 0 && ny >= 0 && nx < table.size() && ny <table[0].size()){
                if(!vis[nx][ny] && table[nx][ny] == num){
                    vis[nx][ny] = true;
                    q.push({nx,ny});
                    minX = min(minX, nx);
                    minY = min(minY, ny);
                    maxX = max(maxX, nx);
                    maxY = max(maxY, ny);
                }
            }
        }
    }

    int vertical = abs(maxX - minX) + 1;
    int horizontal = abs(maxY - minY) + 1;
    vector<vector<int>> ret(vertical, vector<int>(horizontal, 0));

    for(int i = minX; i<=maxX; i++){
        int i2 = i - minX;
        for(int j = minY; j<=maxY; j++){
            int j2 = j - minY;
            if(table[i][j] == num){
                ret[i2][j2] = 1;
            }
        }
    }

    return ret;
}

이 함수는 BFS 탐색을 사용하여 테이블 위의 퍼즐 조각을 추출합니다. 추출된 조각은 최소 크기의 격자판으로 반환됩니다.

모양 비교 및 퍼즐 채우기

bool matchShape(vector<vector<int>>& emptyShape, vector<vector<int>>& shape) {
    if (emptyShape.size() != shape.size() || emptyShape[0].size() != shape[0].size()) return false;
    for (int i = 0; i < emptyShape.size(); i++) {
        for (int j = 0; j < emptyShape[0].size(); j++) {
            if (emptyShape[i][j] != shape[i][j]) return false;
        }
    }
    return true;
}

이 함수는 빈칸의 모양과 퍼즐 조각의 모양이 일치하는지 확인합니다. 사이즈나 내용이 하나라도 다르면 false를 반환합니다.

solution 함수

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    vector<vector<vector<int>>> shapes;
    vector<vector<vector<int>>> emptyShapes;
    visited.resize(table.size(), vector<bool>(table[0].size(), false));
    visited2.resize(table.size(), vector<bool>(table[0].size(), false));

    for(int i = 0; i<table.size(); i++){
        for(int j = 0; j<table[i].size(); j++){
            if(!visited[i][j] && table[i][j] == 1){
                shapes.push_back (bfsShape(table, i, j,1,visited));
            }
        }
    }

    for(int i = 0; i<table.size(); i++){
        for(int j = 0; j<table[i].size(); j++){
            if(!visited2[i][j] && game_board[i][j] == 0){
                emptyShapes.push_back (bfsShape(game_board, i, j,0, visited2));
            }
        }
    }

    vector<bool> used(shapes.size(), false);

    for(auto empty : emptyShapes){
        bool matched = false;
        for(int i = 0; i<shapes.size(); i++){
            if(used[i]) continue;
            auto rotations = rotate(shapes[i]);

            for(auto rShape : rotations){
                if(matchShape(empty, rShape)){
                    used[i] = true;
                    answer += countOnes(rShape);
                    matched = true;
                    break;
                }
            }
            if(matched) break;
        }
    }
    return answer;
}