🌞문제

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

🌞접근법

조건1. 테이블 위에 놓인 퍼즐 조각을 게임 보드위에 빈공간에 적절히 올려놓을 것이다. 게임 보드와 테이블은 모두 1x1크기의 정사각 격자모양이다.
조건2. 조각은 한 번에 하나씩 채워 넣을 수 있다.
조건3. 조각은 회전시킬 수 있다.
조건4. 조각을 뒤집을 수는 없다.
조건5. 게임 보드에 새로 채워 넣은 조각과 인접한 칸이 비어 있으면 안된다.
조건6. 게임보드의 행의 길이는 3~50
조건7. 게임보드의 열의 길이 = 게임보드의 행의 길이
조건8. 퍼즐 조각이 놓일 빈칸은 1~6개만 이용

구해야 하는 값 : 조건을 만족하면서 최대한 많은 조각을 채워 넣는 경우의 총 몇칸을 채우는지를 return해라.

그러기 위해서는 먼저 하나의 도형을 이루는 table의 요소들을 하나의 vector에 저장을하고 이를 저장하여야 한다.

그리고 이와 같은지를 비교하기 위한 게임보드의 빈칸 요소들도 저장을 하여야 한다.

이것들을 찾는 방법은 dfs와 bfs중 하나를 이용하면 될 것으로 보인다.

풀이에서는 bfs를 선택해서 풀어보도록 하겠다.

그렇게해서 각각의 퍼즐과 빈칸의 요소를 하나의 벡터안에서 관리를 할 수 있게 저장을 했다면,
이 값들을 상대적인 값으로 변경하기 위하여 (0,0)을 시작으로하여 도형이 들어가게끔 값들을 수정해준다.

이렇게 구해진 game_board의 값들은 sort를 해주어야 한다. 그 이유는 table의 요소와 비교를하여 배열의 요소를 각각 비교해주기 위해서는
대응하는 배열의 요소를 정리해주어야 하기 때문이다.

이렇게해서 상대적인 값으로 변한 배열인 empty_board의 각 요소들과
table의 요소들을 모두 비교하여 맞는 것이 있는지를 확인한다.

그리고 table의 요소는 회전이 가능하기 때문에 90도를 회전시킨 이후에 다시 sort를 하고 empty_board의 값들과 비교를 해준다.

회전을 시키는 방법은

가상의 정사각형을 만들어서 그 안에서 요소들을 90도 회전 시킨다.

🌞풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>

using namespace std;

int size1;
int size2;

int cnt = 0;
vector<vector<int>> game_board;
vector<vector<int>> table;

vector<vector<pair<int,int>>> empty_board;
vector<vector<pair<int,int>>> puzzle;

queue<pair<int,int>> q;
queue<pair<int,int>> q2;

int visit[51][51];
int visit1[51][51];

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

void bfs(vector<vector<int>> obj,vector<vector<pair<int,int>>> &res, int visit[][51])
{
    for(int i=0;i<obj.size();i++)
    {
        for(int j=0;j<obj.size();j++)
        {
            if(obj[i][j] == 1) q.push(make_pair(i,j));
        }
    } 
    
    while(!q.empty())
    {   
        vector<pair<int,int>> elem;
        elem.clear();
        q2.push(q.front());
        int flag = 1;
        if(visit[q.front().first][q.front().second] == 1)
        {
            flag = 0;
        }
        else
        {
            visit[q.front().first][q.front().second] = 1;
            elem.push_back(make_pair(q.front().first,q.front().second));
        }
        q.pop();
        
        
        
        while(!q2.empty() && flag == 1)
        {
            int y=q2.front().first;
            int x=q2.front().second;
            q2.pop();
            
            
            for(int i=0;i<4;i++)
            {
                int my = y + dy[i];
                int mx = x + dx[i];
                
                if(my > -1 && mx > -1 && my <obj.size() && mx <obj.size() && obj[my][mx] == 1 && visit[my][mx] == 0)
                {
                    elem.push_back(make_pair(my,mx));
                    q2.push(make_pair(my,mx));
                    visit[my][mx] = 1;
                }    
            }
        }
        sort(elem.begin(),elem.end());
        if(!elem.empty()) res.push_back(elem);
    }

    while(!q.empty())
    {
        q.pop();
    }
    
    while(!q2.empty())
    {
        q2.pop();
    }
}

void resize(vector<vector<pair<int,int>>> &obj)
{
 
    for(int i=0;i<obj.size();i++)
    {
        int miny = 60;
        int minx = 60;
        for(int j=0;j<obj[i].size();j++)
        {
            if(obj[i][j].first < miny) miny = obj[i][j].first;
            if(obj[i][j].second < minx) minx = obj[i][j].second;
        }
        
        for(int j=0;j<obj[i].size();j++)
        {
            obj[i][j].first -= miny;
            obj[i][j].second -= minx;
        }
    }
}

void Rotation()
{
    int rect = -1;
    for(int i=0;i<puzzle.size();i++)
    {
        for(int j=0;j<puzzle[i].size();j++)
        {
            if(rect < puzzle[i][j].first) rect = puzzle[i][j].first;
            if(rect < puzzle[i][j].second) rect = puzzle[i][j].second;
        }
    }
    
    for(int i=0;i<puzzle.size();i++)
    {
        for(int j=0;j<puzzle[i].size();j++)
        {
            puzzle[i][j] = make_pair(rect - puzzle[i][j].second, puzzle[i][j].first);
        }
        sort(puzzle[i].begin(),puzzle[i].end());
    }
    
    resize(puzzle);
}

void Compare()
{
    for(int i=0;i<empty_board.size();i++)
    {
        for(int j=0;j<puzzle.size();j++)
        {
            int flag = 1;
            if(empty_board[i].size() == puzzle[j].size())
            {
                for(int k=0;k<puzzle[j].size();k++)
                {
                    if((empty_board[i][k].first != puzzle[j][k].first) || (empty_board[i][k].second != puzzle[j][k].second))
                    {
                        flag = 0;
                        break;
                    }
                }
                if(flag == 1)
                {
                    cnt+=puzzle[j].size();
                    empty_board.erase(empty_board.begin()+i);
                    puzzle.erase(puzzle.begin()+j);
                    i--;
                }
            }
            
        }
    }
}

int solution(vector<vector<int>> _game_board, vector<vector<int>> _table) {
    
    for(int i=0;i<_game_board.size();i++)
    {
        for(int j=0;j<_game_board[0].size();j++)
        {
            if(_game_board[i][j] == 0) _game_board[i][j] = 1;
            else _game_board[i][j] = 0;
        }
    }
    
    game_board = _game_board;
    table = _table;
    
    bfs(game_board,empty_board,visit);
    bfs(table,puzzle,visit1);
    
    // for(int i=0;i<empty_board.size();i++)
    // {
    //     for(int j=0;j<empty_board[i].size();j++)
    //     {
    //         cout << "[" << empty_board[i][j].first << ", " << empty_board[i][j].second <<  "]"<< " "; 
    //     }
    //     cout << endl;
    // }
    // for(int i=0;i<puzzle.size();i++)
    // {
    //     for(int j=0;j<puzzle[i].size();j++)
    //     {
    //         cout << "[" << puzzle[i][j].first << ", " << puzzle[i][j].second <<  "]"<< " "; 
    //     }
    //     cout << endl;
    // } 
    
    cout<<endl;
    resize(empty_board);
    resize(puzzle);
    
    size1 = empty_board.size();
    size2 = puzzle.size();
    
    for(int i=0;i<puzzle.size();i++)
    {
        for(int j=0;j<puzzle[i].size();j++)
        {
            cout << "[" << puzzle[i][j].first << ", " << puzzle[i][j].second <<  "]"<< " "; 
        }
        cout << endl;
    }
    
    cout<<endl;
    
    for(int i=0;i<empty_board.size();i++)
    {
        for(int j=0;j<empty_board[i].size();j++)
        {
            cout << "[" << empty_board[i][j].first << ", " << empty_board[i][j].second <<  "]"<< " "; 
        }
        cout << endl;
    }

    
    Compare();
    
    cout << cnt;
    

    
    Rotation();

    Compare();
    Rotation();

    Compare();
    
    Rotation();
    Compare();
    
    return cnt;
}

정말 이거 풀면서 울고 싶었다..
하아..