퍼즐 조각 채우기 84021

문제

접근 방법

처음에는 위에서 본 모습, 왼쪽에서 본 모습 등으로 해결할 수 있을 것 같았다.

O
O	O	O
		O

위 2 1 2 왼쪽 1 3 1

		O
O	O	O
O

위 2 1 2 왼쪽 1 3 1
안된다는 것을 알게 됐다.
경로를 기록하는 방법도 생각해봤다. 바로 위의 예시로 하자면 우로 3칸, 위로 1칸, 아래로 1칸 이런 식으로 말이다. 하지만 겹치는 부분이 많을 것 같고 시작점에 따라 달라질 수 있으니 안될 것 같았다.
각 지점의 시작점으로 할법한 곳을 골라서 탐색을 같이해보는 것을 생각해봤다. 하지만 시작점을 고르는 것이 힘들고 회전된 경우를 생각하면 힘들 것 같았다.

그래서 다른 사람 풀이를 보기로 했다.
점을 저장하고 0으로 맞춘 뒤 회전하며 확인하는 방법으로 푸는 것이었다. 당연한 것 같으면서도 내가 생각해내지 못해서 아쉬웠다.

코드

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pos;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, H, W;
void getBlocks(vector<vector<int>> &tableVec, vector<vector<pos>> &blockVec, int fill) // 블록을 가져오는 BFS
{
    queue<pos> bfs;
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (tableVec[i][j] == fill)
                continue;
            vector<pos> block;
            bfs.push({i, j});
            tableVec[i][j] = fill;
            block.push_back({i, j});
            while (!bfs.empty())
            {
                pos cur = bfs.front();
                bfs.pop();
                for (int i = 0; i < 4; ++i)
                {
                    pos next = {cur.first + dy[i], cur.second + dx[i]};
                    if (next.first < 0 || next.second < 0 || next.first >= H || next.second >= W)
                        continue;
                    if (tableVec[next.first][next.second] == fill)
                        continue;
                    tableVec[next.first][next.second] = fill;
                    bfs.push(next);
                    block.push_back(next);
                }
            }
            blockVec.push_back(block);
        }
    }
}
pos getMinBlock(vector<pos> &block) // 위치 조정을 위한 최솟값
{
    pos min = {51, 51};
    for (pos p : block)
    {
        if (min.first > p.first)
            min.first = p.first;
        if (min.second > p.second)
            min.second = p.second;
    }
    return min;
}
void sortBlock(vector<vector<pos>> &blockVec) // 최솟값으로 빼주어 0으로 맞춘 뒤 정렬
{
    for (int i = 0; i < blockVec.size(); ++i)
    {
        auto block = blockVec[i];
        pos min = getMinBlock(block);
        for (int j = 0; j < block.size(); ++j)
        {
            block[j].first -= min.first;
            block[j].second -= min.second;
        }
        sort(block.begin(), block.end());
        blockVec[i] = block;
    }
}
void rotateBlock(vector<vector<pos>> &blocks) // 회전
{
    for (int i = 0; i < blocks.size(); ++i)
    {
        auto block = blocks[i];
        for (int j = 0; j < block.size(); ++j)
        {
            int temp = block[j].first;
            block[j].first = -block[j].second;
            block[j].second = temp;
        }
        blocks[i] = block;
    }
}
int insertBlock(vector<vector<pos>> &boards, vector<vector<pos>> &blocks) // 동일한 부분을 제거해주며 진행
{
    int ret = 0;
    queue<pos> bfs;
    for (int k = 0; k < 4; ++k)
    {
        sortBlock(blocks);
        for (int i = 0; i < boards.size();)
        {
            bool isFind = false;
            for (int j = 0; j < blocks.size(); ++j)
            {
                if (boards[i] == blocks[j])
                {
                    ret += blocks[j].size();
                    blocks.erase(blocks.begin() + j);
                    isFind = true;
                    break;
                }
            }
            if (isFind)
                boards.erase(boards.begin() + i);
            else
                ++i;
        }
        rotateBlock(blocks);
    }
    return ret;
}
int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    vector<vector<pos>> boards, blocks;
    H = game_board.size();
    W = game_board[0].size();
    getBlocks(table, blocks, 0);
    getBlocks(game_board, boards, 1);
    sortBlock(boards);
    return insertBlock(boards, blocks);
}

풀이

항상 느끼지만 방법을 알고나면 쉬워보인다.
문제가 복잡한 만큼 중복되는 부분은 함수로 빼주는 게 좋다.
블록을 가져오는 함수 (게임 보드와 테이블 둘 다 사용한다)
위치 조정을 위해 최솟값을 구하는 함수 (정렬해주는 함수에서 사용한다)
정렬해주는 함수 (게임 보드 블럭은 1번, 테이블 블럭은 반복문에 들어갈 때마다 1번씩)
블럭을 회전해주는 함수 (테이블 블럭은 반복문이 끝날 때마다 1번씩)
블럭을 비교하며 같으면 제거해주는 함수 (중복되진 않지만 길어서 빼주었다)

문제를 어렵게 생각하면 풀리지 않는 것 같다.