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

문제

문제 설명

 

풀이

 

[풀이]

 

처음에 문제를 보고 빈 공간에 조각을 채워넣어야 하는 줄 알고 어렵다고 생각했는데, 조건에 조각을 넣었을 때, 빈 공간이 생기면 안된다는 조건을 보고 생각보다 쉽겠다고 생각했다.

 

하지만 막상 해보니 코드가 엄청 길어지고 처음 생각했던 방법과 다르게 풀어서 의외로 오래 걸렸다...

 

내가 시도한 방법은 조각이 들어갈 수 있는 공간을 탐색하고, 그 공간의 모양을 파악해 90도로 회전해 나올 수 있는 모양들은 전부 같은 모양으로 정했다.

 

그리고 조각의 모양이 90도로 회전해 나올 수 있는 모양 중 하나라면 채워넣는 식으로 코드를 짰다.

 

이후 같은 조각인지 비교하는 방법은 다음 그림과 같이 만들었다.

 

 

만약 위와 같은 퍼즐의 공간이 있다고 하면 공간을 탐색했을 때, y축은 아래로 x축은 오른쪽으로 탐색을 하므로 board[1][0] 에서 탐색을 시작할 것이다.

 

그러면 vector에 조각을 넣을 때, x축의 시작점 만큼 빼서

 

 

위 와 같이 크기가 6인 vector<vector<int>>에 조각을 저장한다.

 

이 때, 좀 더 편의를 위해 모든 수가 0보다 작지 않도록 만들어 주는 reSize를 할 것이다.

 

reSize는 가장 작은 수를 찾아서 그 수만큼 빼는 방법인데 쉽게 말하면 6*6 공간에서 조각을 왼쪽으로 밀착시켜서 다시 모양을 vector로 바꾸는 것이다. reSize를 하면 아래와 같이 조각의 vector가 변경된다.

 

 

이렇게 하면 장점이 조각을 회전시킬 때 편하다.

 

이제 이 조각을 회전시켜서 나올 수 있는 모양들을 전부 찾아야 하는데, reSize된 모양을 기준으로 90도 회전을 하면 조각을 다음과 같이 변경할 수 있다는 사실을 알 수 있다.

 

 

회전 전의 x축은 회전 후의 y축으로 그대로 가고 회전 전의 y축은 -1을 곱한다음 높이만큼 더해주면 된다는 사실을 알 수 있다.

 

그러므로 90도 회전을 구현하고, 3번 실행해 돌렸을 경우 나오는 모든 모양을 찾았다.

​

이후 퍼즐에 넣을 수 있는 조각이 퍼즐에서 갖고 있는 조각과 일치하는지 비교하고 만약 넣을 수 있는 공간이 남아있다면, 넓이에 더해 최종적으로 나올 수 있는 넓이를 return하도록 코드를 구현했다.

​

​

[아이디어 정리]

 

1. 퍼즐을 넣을 수 있는 공간을 2차원 vector로 찾는다.
2. 퍼즐을 넣을 수 있는 공간을 회전해 나올 수 있는 모든 모양을 찾는다. 이 때, 이러한 공간이 몇개 있는지 Count해 중복된 공간은 Count를 1 증가시킨다.
3. ​내가 가지고 있는 조각의 모습이 퍼즐을 넣을 수 있는 공간 중에 있는지 찾고 있다면 Count를 -1 해주고, 넓이에 크기만큼 더해준다.​
4. 최종 넓이를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

struct puzzle
{
    int puzzleSize=0;
    int puzzleCnt=0;
    vector<vector<vector<int>>> allPuzzle;
    
    bool cmpPuzzle(vector<vector<int>> ppp)
    {
        bool flag=true;
        for (int i=0; i<4; i++)
        {
            flag=true;
            for (int j =0; j<allPuzzle[i].size(); j++)
            {
                if (ppp[j]!=allPuzzle[i][j])
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                return true;
            }
        }
        return false;
    }
};

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int puzzleY,puzzleX;
vector<vector<int>> realGameBoard;
vector<vector<int>> realTable;

vector<puzzle> puzzleList;


vector<vector<int>> reSize(vector<vector<int>> thisBlock)
{
    int minV=7;
    int blockCnt=0;
    for (int i=0; i<6; i++)
    { 
        if (thisBlock[i].size()>0 && thisBlock[i][0]<minV)
        {
            minV=thisBlock[i][0];
        }
    }
    for (int i=0; i<6; i++)
    {
        for (int j=0; j<thisBlock[i].size(); j++)
        {
            thisBlock[i][j]-=minV;
        }
    }
    return thisBlock;
}

vector<vector<int>> rotationBlock(vector<vector<int>> thisBlock)
{
    // 90도 회전 구하기
    vector<vector<int>> new90Block(6);
    for (int i=0; i<6;i++)
    {
        for(int j=0; j<thisBlock[i].size(); j++)
        {
            new90Block[thisBlock[i][j]].push_back(-i);
        }
    }
    for (int i=0; i<6; i++)
    {
        sort(new90Block[i].begin(),new90Block[i].end());
    }
    new90Block = reSize(new90Block);
    return new90Block;
}

void makePuzzle(vector<vector<int>> thisBlock)
{
    puzzle newPuzzle;
    newPuzzle.puzzleCnt=1;
    for(int i=0; i<6; i++)
    {
        newPuzzle.puzzleSize+=thisBlock[i].size();
    }
    newPuzzle.allPuzzle.push_back(thisBlock);
    vector<vector<int>> c;
    // 첫 90회전
    c=rotationBlock(thisBlock);
    newPuzzle.allPuzzle.push_back(c);
    // 두번째 90회전
    c=rotationBlock(c);
    newPuzzle.allPuzzle.push_back(c);
    // 세번째 90회전
    c=rotationBlock(c);
    newPuzzle.allPuzzle.push_back(c);
    puzzleList.push_back(newPuzzle);
}

int makePuzzleList(vector<vector<int>> thisBlock, bool isMake) //isMake라면 만드는 단계
{
    if (isMake)
    {
        bool havePuzzle=false;
        for (int i=0; i<puzzleList.size(); i++)
        {
            if (puzzleList[i].cmpPuzzle(thisBlock))
            {
                havePuzzle=true;
                puzzleList[i].puzzleCnt+=1;
                break;
            }
        }
        if (!havePuzzle) // 퍼즐 리스트에 없다면
        {
            makePuzzle(thisBlock);
        }
    }
    else
    {
        for (int i=0; i<puzzleList.size(); i++)
        {
            if (puzzleList[i].puzzleCnt>0)
            {
                if (puzzleList[i].cmpPuzzle(thisBlock))
                {
                    puzzleList[i].puzzleCnt-=1;
                    return puzzleList[i].puzzleSize;
                }
            }
        }
    }
    return 0;    
}


vector<vector<int>> SearchPuzzle(int y, int x, bool isBoard) //BT가 true면 board
{
    vector<vector<int>> thisBlock(6);// 위로 가는 경우는 없음 탐색을 오른쪽, 아래로 탐색하기 때문, 7이란 숫자는 나올 수 없음
    vector<pair<int,int>> stack;
    pair<int,int> nowSeat=make_pair(y,x);
    int ny, nx;
    thisBlock[0].push_back(0);
    if (isBoard)
    {
        realGameBoard[y][x]=1;
    }
    else
    {
        realTable[y][x]=0;
    }
    stack.push_back(nowSeat);
    while (stack.size()>0)
    {
        nowSeat=stack.back();
        stack.pop_back();
        for (int i=0; i<4; i++)
        {
            ny = nowSeat.first+dy[i];
            nx = nowSeat.second+dx[i];
            if (isBoard)
            {
                if (ny>=0&& ny<puzzleY && nx>=0 && nx<puzzleX && realGameBoard[ny][nx]==0)
                {
                    realGameBoard[ny][nx]=1;
                    stack.push_back(make_pair(ny,nx));
                    thisBlock[ny-y].push_back(nx-x);
                }
            }
            else
            {
                if (ny>=0&& ny<puzzleY && nx>=0 && nx<puzzleX && realTable[ny][nx]==1)
                {
                    realTable[ny][nx]=0;
                    stack.push_back(make_pair(ny,nx));
                    thisBlock[ny-y].push_back(nx-x);
                }
            }            
        }
    }
    for (int i=0; i<thisBlock.size(); i++)
    {
        sort(thisBlock[i].begin(), thisBlock[i].end());
    }
    return reSize(thisBlock);
}

int solution(vector<vector<int>> game_board, vector<vector<int>> table) {
    realGameBoard = game_board;
    realTable=table;
    puzzleY=game_board.size();
    puzzleX=game_board[0].size();
    for (int i=0; i<puzzleY; i++)
    {
        for(int j=0;j<puzzleX; j++)
        {
            if (realGameBoard[i][j]==0)
            {
                makePuzzleList(SearchPuzzle(i, j,true),true);
            }
        }

 

---

 

코드의 길이가 보면 정말 긴데 처음에 아무 생각없이 처음 시작점과 끝점으로 조각을 구현했다가 그렇게 하면 0,1,2와 0,2 의 조각이 0,2로 동일하게 나와 문제가 생긴다는 점을 깨닫고 구조체를 만들어 다시 구현했다.

 

덕분에 돌고 돌아 더 고생했다.. ㅠㅠㅠ

구현 문제는 왤케 시간이 오래걸리는거 같지...

 

프로그래머스