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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 3주차

1. 주의할 점

- 구현할 부분이 많으니 헷갈리지 않도록 변수명 및 함수명을 잘 작성한다

 

2. 구현

- 가로/세로의 최대길이가 50이므로 브루트포스나 DFS를 사용해도 될 것 같다 → 시도

- 각 변수에 대한 설명은 아래 주석을 참고한다

- 이 문제의 중점은 퍼즐조각의 기준점을 잡고, 기준점으로부터 동일 퍼즐조각의 나머지 부분이 기준점으로부터 URDL(상우하좌) 몇 칸씩 떨어져있는지 미리 구해서 puzzle[] 벡터에 저장한다

- initialize() 함수를 통해 check[][] 배열을 0으로 초기화한다

- calArea() 함수를 통해 Arr[][] 배열과 Check[][] 배열을 채운다

- dfs() 함수를 통해 Arr[][] 배열의 모든 원소를 훑으며, 퍼즐조각이 들어갈 수 있고, 아직 채워지지 않았으며, 검사하려는 퍼즐조각과 크기가 같은 경우에 퍼즐을 각각 0,90,180,270도 회전시켜서 대입해본다

- 이때, 회전한 이후 퍼즐의 조각은 puzzle[]에 저장된 퍼즐조각의 정보를 통해서 구한다

- 퍼즐조각의 기준점으로부터 URDL이 (0,1,1,0)인 조각이 있다면, 90도를 회전시키면 원소의 값을 오른쪽으로 한칸씩 움직이는것과 같다. 따라서 (0,1,1,0)→(0,0,1,1)의 위치에 있다고 볼 수 있다. 만약 180도 회전이면 오른쪽으로 2칸을 움직이면 된다

- 위의 방법을 통해 일치하는 퍼즐조각의 최대수를 구한다

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
struct info{
    int y,x,u,r,d,l;
};
struct info2{
    int y,x;
};
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int mul[4]={1,1,-1,-1};
vector<info> puzzle[25*25];     //그룹퍼즐 정보 저장
bool puzzleUsed[25*25]={false,};      //그룹퍼즐 사용 여부
bool covered[25*25]={false,};       //땅 채워짐 여부
int check[50][50];      //땅덩어리 그룹번호 저장
int num, cnt=0, areaNum=0;        //가로세로, 퍼즐 수, 땅덩어리 수
int arr[50][50];        //땅덩어리 크기

void initialize(){
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++)
            check[i][j]=0;
}

void calArea(vector<vector<int>> game_board){
    initialize();
    for(int i=0;i<num;i++)
        for(int j=0;j<num;j++){
            if(check[i][j] || game_board[i][j]==1) continue;
            queue<info2> q;
            vector<info2> v;
            check[i][j]=++areaNum;
            int val=1;
            q.push({i,j});
            v.push_back({i,j});
            while(!q.empty()){
                int cx = q.front().x;
                int cy = q.front().y;
                q.pop();
                for(int k=0;k<4;k++){
                    int nx = cx+dx[k];
                    int ny = cy+dy[k];
                    if(nx>=0 && ny>=0 && nx<num && ny<num && game_board[ny][nx]==0 && check[ny][nx]==0){
                        check[ny][nx]=areaNum;
                        val++;
                        q.push({ny,nx});
                        v.push_back({ny,nx});
                    }
                }
            }
            for(int k=0;k<v.size();k++)
                arr[v[k].y][v[k].x]=val;
        }
}

int dfs(){
    int result=0;
    for(int i=0;i<num;i++){
        for(int j=0;j<num;j++){
            int val = arr[i][j];            //크기
            if(val==0) continue;
            int aNum = check[i][j];
            if(covered[aNum]) continue;     //해당 땅이 채워진 경우
            for(int k=0;k<cnt;k++){     //퍼즐로 채워보자
                if(puzzleUsed[k] || puzzle[k].size()+1!=val) continue;      //퍼즐이 사용됐거나 땅의 크기가 퍼즐의 크기와 같지 않다면
                bool avail=false;
                //매치 시도
                for(int m=0;m<4;m++){       //4방향 회전
                    avail=true;
                    for(int n=0;n<puzzle[k].size();n++){
                        int up = puzzle[k][n].u;
                        int down = puzzle[k][n].d;
                        int right = puzzle[k][n].r;
                        int left = puzzle[k][n].l;
                        int mm = m;
                        while(mm--){
                            int temp = left;
                            left=down;
                            down=right;
                            right=up;
                            up=temp;
                        }
                        int ny = i-up+down;
                        int nx = j+right-left;
                        if(nx<0 || ny<0 ||nx>=num || ny>=num || check[ny][nx]!=aNum){       //범위를 벗어났거나, 채워야할 부분이 아닌 경우
                            avail=false;
                            break;
                        }
                    }
                    if(avail){
                        covered[aNum]=true;
                        puzzleUsed[k]=true;
                        result+=val;
                        break;
                    }
                }
                if(avail) break;
            }
        }
    }
    return result;
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    num = game_board.size();
    initialize();
    for(int i=0;i<num;i++){
        for(int j=0;j<num;j++){
            if(table[i][j]!=1) continue;
            if(check[i][j]) continue;
            queue<info> q;
            check[i][j]=1;
            q.push({i,j,0,0,0,0});
            while(!q.empty()){
                int cx = q.front().x;
                int cy = q.front().y;
                int cu = q.front().u;
                int cd = q.front().d;
                int cr = q.front().r;
                int cl = q.front().l;
                q.pop();
                for(int k=0;k<4;k++){
                    int nx = cx+dx[k];
                    int ny = cy+dy[k];
                    if(nx>=0 && ny>=0 && nx<num && ny<num && check[ny][nx]==0){
                        check[ny][nx]=1;
                        if(table[ny][nx]!=1) continue;
                        if(k==0){    
                            q.push({ny,nx,cu+1,cr,cd,cl});
                            puzzle[cnt].push_back({0,0,cu+1,cr,cd,cl});
                        }
                        else if(k==1){
                            q.push({ny,nx,cu,cr+1,cd,cl});
                            puzzle[cnt].push_back({0,0,cu,cr+1,cd,cl});
                        }
                        else if(k==2){
                            q.push({ny,nx,cu,cr,cd+1,cl});
                            puzzle[cnt].push_back({0,0,cu,cr,cd+1,cl});
                        }
                        else{
                            q.push({ny,nx,cu,cr,cd,cl+1});
                            puzzle[cnt].push_back({0,0,cu,cr,cd,cl+1});
                        }
                    }
                }
            }
            cnt++;
        }
    }
    calArea(game_board); 
    return dfs();
}