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

문제

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

프로그래머스 퍼즐 조각 채우기

프로그래머스 퍼즐 조각 채우기

프로그래머스 퍼즐 조각 채우기

 

문제 내용

table에 놓인 도형들을, 최대한 game_board에 채워 넣어야 한다. 

단, 도형은 딱 맞는 곳에만 들어갈 수 있다. (넣었을 때 옆에 공백이 남으면 안 된다.)

도형을 집어넣을 때, 조각을 회전시킬 수는 있지만, 뒤집을 수는 없다.

 

최대한 많은 조각을 채워 넣었을 때, 몇 칸을 채워 넣은 것인지를 구하면 된다.

 

문제 풀이

table의 도형이, game_board의 빈칸에 완벽하게 들어가야 하기 때문에, table과 game_board에서 도형과 빈칸을 각각 추출해야 한다. 

그리고 해당 도형들을 매칭시켜주면 되는데, 이때 도형을 돌릴 수도 있다.

 

1. 도형/빈칸 추출

int dr[4]={1,-1,0,0};
int dc[4]={0,0,1,-1};

// 좌표들을 가지고, 도형에 최대한 감싸는 배열을 만듬
vector<vector<bool>> makePuzzleArr(vector<pair<int,int>> & puzzle){
    int minR=100, minC=100, maxR=-1, maxC=-1;
    for(int i=0;i<puzzle.size();i++){
        minR=min(minR, puzzle[i].first);
        maxR=max(maxR, puzzle[i].first);
        
        minC=min(minC,puzzle[i].second);
        maxC=max(maxC, puzzle[i].second);
    }
    
    int rowSize= maxR-minR+1;
    int colSize= maxC-minC+1;
    
    vector<vector<bool>> result(rowSize,vector<bool>(colSize,false));
    
    for(int i=0;i<puzzle.size();i++){
        int nr= puzzle[i].first-minR;
        int nc= puzzle[i].second-minC;
        
        result[nr][nc]=true;
    }

    return result;
}

// 도형을 추출하는 함수
vector<vector<vector<bool>>> extractSpace(vector<vector<int>>& arr, int spaceType){
    queue<pair<int,int>> q;
    vector<vector<int>> vis(n, vector<int>(n, 0));
    vector<vector<vector<bool>>> result;
    
    int cnt=0;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(arr[i][j]!=spaceType || vis[i][j]!=0) continue;
            
            q.push({i,j}); //추가
            vis[i][j]=++cnt; //1부터 대입
            
            vector<pair<int,int>> puzzle;
            puzzle.push_back({i,j});
            
            while(!q.empty()){
                auto point = q.front();
                q.pop();
                
                for(int k=0;k<4;k++){
                    int nr=dr[k] + point.first;
                    int nc=dc[k] + point.second;
                    
                    if(nr>=0 && nc>=0 && nr<n && nc<n && arr[nr][nc]==spaceType && vis[nr][nc]==0){
                        //여기서 추가
                        q.push({nr,nc});
                        vis[nr][nc]=cnt;
                        puzzle.push_back({nr,nc});
                    }
                }
            }
            
            // 퍼즐의 처리
            auto puzzle_result=makePuzzleArr(puzzle);
            result.push_back(puzzle_result);
        }
    }
    
    return result;
}

 

2. 도형과 빈칸을 비교

// 도형(빈칸)을 감싼 배열의 크기
int calcArrSize(vector<vector<bool>> & arr){    
    int rowSize=arr.size();
    int colSize=arr[0].size();

    return rowSize*colSize;
}

// 도형과 빈칸이 같은지 비교
bool compareArr(vector<vector<bool>> &board, vector<vector<bool>> &table){
    int rowSize=board.size();
    int colSize=board[0].size();
    
    for(int i=0;i<rowSize;i++){
        for(int j=0;j<colSize;j++){
            if(board[i][j] != table[i][j]) return false;
        }
    }    
    
    return true;
}

// 도형 회전
vector<vector<bool>> rotatePuzzle(vector<vector<bool>> &arr){
    int rowSize=arr.size(); //원래의 행 (세로 길이)
    int colSize=arr[0].size(); //원래의 열 (가로 길이)
    
    vector<vector<bool>> result;

    for(int i=0;i<colSize;i++){ //원래의 열
        vector<bool> makeRow;
        for(int j=rowSize-1;j>=0;j--){ // 원래의 행
            makeRow.push_back(arr[j][i]);
        }        
        result.push_back(makeRow);
    }
    
    return result;
}

// 도형을 감싼 배열에서 도형이 몇칸을 차지하는지 계산
int calcPuzzleSize(vector<vector<bool>> &arr){
    int num=0;
    for(int i=0;i<arr.size();i++){
        for(int j=0;j<arr[0].size();j++){
            if(arr[i][j]) num++;
        }
    }

    return num;
}

// 도형과 빈칸을 비교 (안 맞으면 도형을 회전시킴)
int comparePuzzle(vector<vector<bool>> &board, vector<vector<bool>> &table){
    //board는 가만히 두고, table만 바꿈
    bool result=false;
    for(int i=0;i<4;i++){
        if(board.size()!=table.size() || board[0].size()!=table[0].size()){
            //테이블 회전
            table=rotatePuzzle(table);
            continue;
        }
        
        result = compareArr(board, table);
        if(result) return calcPuzzleSize(table);
        else{
            //테이블 회전
            table=rotatePuzzle(table);
        }
    }
    return 0;
}

 

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;
int dr[4]={1,-1,0,0};
int dc[4]={0,0,1,-1};

// 좌표들을 가지고, 도형에 최대한 감싸는 배열을 만듬
vector<vector<bool>> makePuzzleArr(vector<pair<int,int>> & puzzle){
    int minR=100, minC=100, maxR=-1, maxC=-1;
    for(int i=0;i<puzzle.size();i++){
        minR=min(minR, puzzle[i].first);
        maxR=max(maxR, puzzle[i].first);
        
        minC=min(minC,puzzle[i].second);
        maxC=max(maxC, puzzle[i].second);
    }
    
    int rowSize= maxR-minR+1;
    int colSize= maxC-minC+1;
    
    vector<vector<bool>> result(rowSize,vector<bool>(colSize,false));
    
    for(int i=0;i<puzzle.size();i++){
        int nr= puzzle[i].first-minR;
        int nc= puzzle[i].second-minC;
        
        result[nr][nc]=true;
    }

    return result;
}

// 도형을 추출하는 함수
vector<vector<vector<bool>>> extractSpace(vector<vector<int>>& arr, int spaceType){
    queue<pair<int,int>> q;
    vector<vector<int>> vis(n, vector<int>(n, 0));
    vector<vector<vector<bool>>> result;
    
    int cnt=0;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(arr[i][j]!=spaceType || vis[i][j]!=0) continue;
            
            q.push({i,j}); //추가
            vis[i][j]=++cnt; //1부터 대입
            
            vector<pair<int,int>> puzzle;
            puzzle.push_back({i,j});
            
            while(!q.empty()){
                auto point = q.front();
                q.pop();
                
                for(int k=0;k<4;k++){
                    int nr=dr[k] + point.first;
                    int nc=dc[k] + point.second;
                    
                    if(nr>=0 && nc>=0 && nr<n && nc<n && arr[nr][nc]==spaceType && vis[nr][nc]==0){
                        //여기서 추가
                        q.push({nr,nc});
                        vis[nr][nc]=cnt;
                        puzzle.push_back({nr,nc});
                    }
                }
            }
            
            // 퍼즐의 처리
            auto puzzle_result=makePuzzleArr(puzzle);
            result.push_back(puzzle_result);
        }
    }
    
    return result;
}

// 도형(빈칸)을 감싼 배열의 크기
int calcArrSize(vector<vector<bool>> & arr){    
    int rowSize=arr.size();
    int colSize=arr[0].size();

    return rowSize*colSize;
}

// 도형과 빈칸이 같은지 비교
bool compareArr(vector<vector<bool>> &board, vector<vector<bool>> &table){
    int rowSize=board.size();
    int colSize=board[0].size();
    
    for(int i=0;i<rowSize;i++){
        for(int j=0;j<colSize;j++){
            if(board[i][j] != table[i][j]) return false;
        }
    }    
    
    return true;
}

// 도형 회전
vector<vector<bool>> rotatePuzzle(vector<vector<bool>> &arr){
    int rowSize=arr.size(); //원래의 행 (세로 길이)
    int colSize=arr[0].size(); //원래의 열 (가로 길이)
    
    vector<vector<bool>> result;

    for(int i=0;i<colSize;i++){ //원래의 열
        vector<bool> makeRow;
        for(int j=rowSize-1;j>=0;j--){ // 원래의 행
            makeRow.push_back(arr[j][i]);
        }        
        result.push_back(makeRow);
    }
    
    return result;
}

// 도형을 감싼 배열에서 도형이 몇칸을 차지하는지 계산
int calcPuzzleSize(vector<vector<bool>> &arr){
    int num=0;
    for(int i=0;i<arr.size();i++){
        for(int j=0;j<arr[0].size();j++){
            if(arr[i][j]) num++;
        }
    }

    return num;
}

// 도형과 빈칸을 비교 (안 맞으면 도형을 회전시킴)
int comparePuzzle(vector<vector<bool>> &board, vector<vector<bool>> &table){
    //board는 가만히 두고, table만 바꿈
    bool result=false;
    for(int i=0;i<4;i++){
        if(board.size()!=table.size() || board[0].size()!=table[0].size()){
            //테이블 회전
            table=rotatePuzzle(table);
            continue;
        }
        
        result = compareArr(board, table);
        if(result) return calcPuzzleSize(table);
        else{
            //테이블 회전
            table=rotatePuzzle(table);
        }
    }
    return 0;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    n=game_board.size();

    auto boardPuzzle=extractSpace(game_board,0);
    auto tablePuzzle=extractSpace(table,1);
    
    int answer=0;
    
    //이미 사용한 빈칸/도형인지 확인하기 위함
    vector<bool> boardUsed(boardPuzzle.size(),false);
    vector<bool> tableUsed(tablePuzzle.size(),false);
    
    for(int i=0;i<boardPuzzle.size();i++){
        for(int j=0;j<tablePuzzle.size();j++){
        	// 도형을 감싼 배열과, 빈칸을 감싼 배열의 크기가 다르면 애초에 들어갈 수 없다.
            // 사용한 도형 or 빈칸은 또 사용할 수 없다.
            if(calcArrSize(boardPuzzle[i]) != calcArrSize(tablePuzzle[j]) 
            	|| boardUsed[i] || tableUsed[j]) continue;
            
            int num=comparePuzzle(boardPuzzle[i], tablePuzzle[j]);            
            if(num>0){
                answer+=num;
                boardUsed[i]=true;
                tableUsed[j]=true;
            }
        }
    }
    
    return answer;
}