[프로그래머스]퍼즐조각 채우기(BFS)

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

왼쪽 board의 빈칸에 table의 블럭을 최대 몇칸 넣을 수 있는지 구하는 문제

단 빈칸과 블럭의 모양은 동일해야 한다 (회전 가능, 대칭 불가)

 

 

 

첫번째 접근 - 빈칸을 연결된 빈칸 수로 나타내봄

board를 순서대로 bfs로 탐색,

ㄱ과 같은 모양은 121,

ㅗ과 같은 모양은 1311

ㅁ 모양은 2222

 

반례가 바로 떠오를정도로 허접했지만 의외로 테케 절반정도를 통과했다

 

위 방식으로 3칸 블럭까진 구별이 가능하고,

대칭을 무시하면 4칸까지 구별 가능하다

ㅡ = 1111 = 4

ㅁ = 2222 = 8

ㄴ = 1121 / 1211 / 2111 = 5

ㄹ = 1221 / 2121 / 2211 = 6

ㅗ = 1311 = 6

합으로 구분한뒤 3이 있으면 ㅗ 아니면 ㄹ

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int n;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<vector<int>> g;
vector<vector<int>> t;
int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    int answer = 0;
    int n = game_board.size();

    for(int y=0 ; y<n ; y++){
        for(int x=0 ; x<n ; x++){
            if(game_board[y][x]==0){
                game_board[y][x]=2;
                queue<pair<int,int>> q;
                vector<int> qq;
                q.push({y,x});
                while(!q.empty()){
                    int y1 = q.front().first;
                    int x1 = q.front().second;
                    q.pop();
                    int zz=0;
                    for(int i=0 ; i<4 ; i++){
                        int ny = y1+dy[i];
                        int nx = x1+dx[i];
                        if (nx>-1 && ny>-1 && nx<n && ny<n){
                            if(game_board[ny][nx]!=1 )
                                zz++;
                        }
                    }
                    qq.push_back(zz);
                    for(int i=0 ; i<4 ; i++){
                        int ny = y1+dy[i];
                        int nx = x1+dx[i];
                        if (nx>-1 && ny>-1 && nx<n && ny<n){
                            if(game_board[ny][nx]==0 ){
                                game_board[ny][nx]=2;
                                q.push({ny,nx});
                            }
                        }
                    }

                }
                g.push_back(qq);
            }
        }
    }
    
    for(int y=0 ; y<n ; y++){
        for(int x=0 ; x<n ; x++){
            if(table[y][x]==1){
                table[y][x]=2;
                queue<pair<int,int>> q;
                vector<int> qq;
                q.push({y,x});
                while(!q.empty()){
                    int y1 = q.front().first;
                    int x1 = q.front().second;
                    q.pop();
                    int zz=0;
                    for(int i=0 ; i<4 ; i++){
                        int ny = y1+dy[i];
                        int nx = x1+dx[i];
                        if (nx>-1 && ny>-1 && nx<n && ny<n){
                            if(table[ny][nx]!=0 )
                                zz++;
                        }
                    }
                    qq.push_back(zz);
                    for(int i=0 ; i<4 ; i++){
                        int ny = y1+dy[i];
                        int nx = x1+dx[i];
                        if (nx>-1 && ny>-1 && nx<n && ny<n){
                            if(table[ny][nx]==1 ){
                                table[ny][nx]=2;
                                q.push({ny,nx});
                            }
                        }
                    }

                }
                t.push_back(qq);
            }
        }
    }
    int counts = 0;
    for(int y=0 ; y<n ; y++){
        for(int x=0 ; x<n ; x++){
            if(game_board[y][x]!=1)
                counts++;
        }
    }
    cout<<counts<<"\n";
    
    for(int y=0 ; y<g.size() ; y++){
        for(int x=0 ; x<g[y].size() ; x++){
            cout<<g[y][x]<<" ";
        }
        cout<<"\n";
    }
    for(int y=0 ; y<t.size() ; y++){
        for(int x=0 ; x<t[y].size() ; x++){
            cout<<t[y][x]<<" ";
        }
        cout<<"\n";
    }
    for(int x=0 ; x<g.size() ; x++){
        for(int y=0 ; y<t.size() ; y++){
            if(g[x]==t[y]){
                cout<<"aa"<<g[x].size()<<"\n";
                answer += g[x].size();
                cout<<"answer"<<answer<<"\n";
                g[x]={-1};
                t[y]={-2};
            }   
        }
    }
    
    
    
    return answer;
}

코드 백업