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

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

코딩테스트 연습 - 3주차

 

 

[난이도] level3
[유형] 브루트포스

[풀이]
board의 빈곳의 모양과, table의 조각의 모양을 각각 2차원 vector에 저장한 뒤 매칭시켜서 몇개나 매칭이 될 수 있는지 구하면 됩니다.
각 모양을 구할 때는 dfs를 이용하여 모양의 좌표들을 저장해주면서 상,하,좌,우 끝값의 좌표를 기록해줍니다.
이것을 알아야 모양의 행과 열과의 길이를 알 수 있고, 올바른 크기의 2차원 vector를 선언하여 좌표를 저장할 수 있습니다.
board 또는 table 중 한쪽의 모양들은 시계방향으로 회전시키며 4방향에 대한 모양을 따로 저장해야 합니다.
아래 코드에서는 vector<vvi> shapes[4],shapes_tb 를 선언하여 shapes에는 빈칸 모양의 4방향 vector를, shapes_tb에는 table의 조각 모양 vector를 저장하였습니다.
4방향을 구할 때는 시계방향으로 90도 돌린 vector를 반환하는 함수를 한개만 선언하면 연속적으로 돌려주면서 4방향을 모두 구할 수 있습니다.

시간 복잡도는 최악의 경우 O((4*50*50)*(50*50)) 정도 나오는것으로 보여 시간내에 AC를 받는 것이 가능합니다.

 

 

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using vvi=vector<vector<int>>;
const int dy[4]={-1,1,0,0}, dx[4]={0,0,1,-1}, inf = 9e8;
vector<vvi> shapes[4],shapes_tb;
bool visit[50][50];
int N,l,r,u,d,scnt,ans;
vector<pair<int,int>> p;
void init(){
    u=l=inf;
    d=r=-inf;
    p.clear();    
}
vvi rotate(vvi& org){
    int r = org[0].size();
    int c = org.size();
    vvi ret = vvi(r,vector<int>(c));

    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            ret[i][j]=org[c-j-1][i];

    return ret;
}
void dfs(int y,int x,int k,vvi& b){
    visit[y][x]=1;
    p.push_back({y,x});
    l=min(l,x),r=max(r,x);
    u=min(u,y),d=max(d,y);

    for(int i=0;i<4;i++){
        int ny=y+dy[i],  nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=N||b[ny][nx]!=k||visit[ny][nx]) continue;
        dfs(ny,nx,k,b);
    }
}
int match(vvi& a,vvi& b){
    if(a.size()!=b.size() || a[0].size() != b[0].size()) return -1;
    int ret=0;
    for(int i=0;i<a.size();i++)
        for(int j=0;j<a[0].size();j++){
            if(a[i][j]+b[i][j]!=1) return -1; 
            ret+=a[i][j];
        }
    return ret;
}
int solution(vvi board,vvi table) {

    N=board.size();
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(!board[i][j] && !visit[i][j]){
                init();
                dfs(i,j,0,board);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,1));
                for(auto& v : p) shape[v.first-u][v.second-l]=0;

                for(int k=0;k<4;k++){
                    shapes[k].push_back(shape);
                    shape=rotate(shape);
                }
            }
        }
    }
    memset(visit,0,sizeof(visit));
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(table[i][j] && !visit[i][j]){
                init();
                dfs(i,j,1,table);
                int row = d-u+1, col = r-l+1;
                vvi shape = vvi(row,vector<int>(col,0));
                for(auto& v : p) shape[v.first-u][v.second-l]=1;
                shapes_tb.push_back(shape);
            }
        }
    }
    vector<bool> filled(shapes[0].size());
    for(auto stb : shapes_tb){
        for(int i=0;i<shapes[0].size();i++){
            if(filled[i]) continue;
            bool ok=false;
            for(int j=0;j<4;j++){
                int ret = match(stb,shapes[j][i]);
                if(ret!=-1){
                    ok=true;
                    ans+=ret;
                    filled[i]=true;
                    break;
                }
            }
            if(ok) break;
        }
    }
    return ans;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level3/위클리_챌린지_3주차.cpp