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

접근

각 game_board와 table 위의 퍼즐 조각들을 (0, 0)을 기준으로 좌표를 옮기는 것까지 생각은 했지만, 

해당 방법의 구현과 또한 퍼즐 조각이 회전이 가능하다는 점에서 구현이 힘들어 아래 블로그를 보고 코드를 따라치며 이해하였다.

 

✔️너무너무 정리가 잘되어 있어 참고하면 좋을 듯 하다!

https://velog.io/@hhj3258/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C%EC%9C%84%ED%81%B4%EB%A6%AC-%EC%B1%8C%EB%A6%B0%EC%A7%80-3%EC%A3%BC%EC%B0%A8-%ED%8D%BC%EC%A6%90-%EC%A1%B0%EA%B0%81-%EC%B1%84%EC%9A%B0%EA%B8%B0

[프로그래머스][C++] 위클리 챌린지 3주차 퍼즐 조각 채우기

 

---

성공 코드

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

int dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};

void GameBoardReversing(vector<vector<int>> &my_board);
vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles);
vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables);
vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles);
int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles);

int solution(vector<vector<int>> game_board, vector<vector<int>> table)
{
    GameBoardReversing(game_board);

    vector<vector<pair<int, int>>> boardBlanks = PuzzleDivision(game_board);

    vector<vector<pair<int, int>>> puzzles = PuzzleDivision(table);

    int answer = PuzzleMatching(boardBlanks, puzzles);

    return answer;
}

void GameBoardReversing(vector<vector<int>> &my_board)
{
    for (int i = 0; i < my_board.size(); i++)
    {
        for (int j = 0; j < my_board[i].size(); j++)
        {
            if (my_board[i][j])
                my_board[i][j] = 0;
            else
                my_board[i][j] = 1;
        }
    }
}

vector<vector<pair<int, int>>> PuzzleReduction(vector<vector<pair<int, int>>> puzzles)
{
    for (int i = 0; i < puzzles.size(); i++)
    {
        int minI = 1000;
        int minJ = 1000;

        for (int j = 0; j < puzzles[i].size(); j++)
        {
            if (puzzles[i][j].first < minI)
                minI = puzzles[i][j].first;

            if (puzzles[i][j].second < minJ)
                minJ = puzzles[i][j].second;
        }

        for (int j = 0; j < puzzles[i].size(); j++)
        {
            puzzles[i][j].first -= minI;
            puzzles[i][j].second -= minJ;
        }
    }

    return puzzles;
}

vector<vector<pair<int, int>>> PuzzleDivision(vector<vector<int>> &tables)
{
    vector<vector<pair<int, int>>> result;
    int new_i = 0;

    while (true)
    {
        vector<pair<int, int>> temp;
        queue<pair<int, int>> q;

        for (int i = new_i; i < tables.size(); i++)
        {
            for (int j = 0; j < tables.size(); j++)
            {
                if (tables[i][j] == 1)
                {
                    q.push(make_pair(i, j));
                    tables[i][j] = 0;
                    new_i = i;
                    break;
                }
            }

            if (!q.empty())
                break;
        }

        if (q.empty())
            break;

        while (!q.empty())
        {
            int cur_i = q.front().first;
            int cur_j = q.front().second;
            temp.push_back(q.front());
            q.pop();

            for(int i=0; i<4; i++){
                int xx=cur_i+dx[i];
                int yy=cur_j+dy[i];
                if(xx>=0 && xx<tables.size() && yy>=0 && yy<tables.size() && tables[xx][yy]==1){
                    q.push(make_pair(xx, yy));
                    tables[xx][yy]=0;
                }
            }
        }

        sort(temp.begin(), temp.end());

        result.push_back(temp);
    }

    result = PuzzleReduction(result);
    return result;
}

vector<vector<pair<int, int>>> PuzzleRotation(vector<vector<pair<int, int>>> puzzles)
{
    for (int i = 0; i < puzzles.size(); i++)
    {
        int N = -1;
        for (int j = 0; j < puzzles[i].size(); j++)
        {
            if (puzzles[i][j].first > N)
                N = puzzles[i][j].first;

            if (puzzles[i][j].second > N)
                N = puzzles[i][j].second;
        }

        for (int j = 0; j < puzzles[i].size(); j++)
            puzzles[i][j] = make_pair(N - puzzles[i][j].second, puzzles[i][j].first);

        sort(puzzles[i].begin(), puzzles[i].end());
    }

    puzzles = PuzzleReduction(puzzles);
    return puzzles;
}

int PuzzleMatching(vector<vector<pair<int, int>>> boardBlanks, vector<vector<pair<int, int>>> puzzles)
{
    int temp_cnt = 1;
    int answer = 0;

    for (int r = 0; r < 4; r++)
    {
        for (int i = 0; i < boardBlanks.size(); i++)
        {
            for (int j = 0; j < puzzles.size(); j++)
            {
                if (boardBlanks[i].size() == puzzles[j].size())
                {
                    int k = 0;
                    for (k = 0; k < boardBlanks[i].size(); k++)
                        if (boardBlanks[i][k] != puzzles[j][k])
                            break;

                    if (k == boardBlanks[i].size())
                    {
                        boardBlanks.erase(boardBlanks.begin() + i);
                        puzzles.erase(puzzles.begin() + j);
                        i--;

                        answer += k;
                        break;
                    }
                }
            } 
        }     

        puzzles = PuzzleRotation(puzzles);
    } 

    return answer;
}