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

2024. 08. 26 - 코딩테스트 스터디 Day84

 
 

01. 문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상, 하, 좌, 우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해 주세요.

 
 

02. 제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

 
 

03. 입출력 예

game_board	table	result
[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]]	[[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]	14
[[0,0,0],[1,1,0],[1,1,1]]	[[1,1,1],[1,0,0],[0,0,0]]	0

 
 
입출력 예 설명
 
입출력 예 #1
입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2
블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

4. 풀이 및 답 

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

using namespace std;
struct Point{
    int x;
    int y;
};

vector<vector<bool> > check;
vector<vector<Point> > puzzleList;
vector<vector<Point> > emptyList;

vector<vector<bool>> rotateOnce(vector<vector<bool> > origin){

    int c = origin.size();
    int r = origin.size();

    vector<vector<bool>> board;
    vector<bool> row(r);

    for(int i = 0; i < c; i++) board.push_back(row);

    for(int i = 0; i < origin.size(); i++){
        for(int j = 0; j < origin[i].size(); j++){
            board[origin.size()-j-1][i] = origin[i][j];
        }
    }
    return board;
}

vector<vector<bool>> fillBoard(vector<Point> p, vector<vector<bool> > board){
    for(int i = 0; i < p.size(); i++){
        int x = p[i].x;
        int y = p[i].y;
        board[x][y] = false;
    }
    return board;
}

vector<Point> getPuzzle(int sx,int sy,vector<vector<bool>> select){
    int dx[] = {0,0,-1,1};
    int dy[] = {-1,1,0,0};
    
    queue<Point> q;
    vector<Point> list;
    check[sx][sy] = true;
    Point p = {sx,sy};
    q.push(p);
    list.push_back(p);


    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= select.size() || ny >= select.size() 
            || check[nx][ny] || !select[nx][ny]) continue;
            check[nx][ny] = true;
            Point np = {nx,ny};
            q.push(np);
            list.push_back(np);
        }
    }
    return list;
}

vector<Point> rePos(vector<Point> p){
    int minX = p[0].x;
    int minY = p[0].y;

    for(int i = 1; i < p.size(); i++){
        minX = min(minX,p[i].x);
        minY = min(minY,p[i].y);
    }

    for(int i = 0; i < p.size(); i++){
        p[i].x -= minX;
        p[i].y -= minY;
    }
    return p;

}

int comparePuzzle(vector<Point> a, vector<Point> b){
    int answer = 0;
    a = rePos(a);
    b = rePos(b);

    int count = 0;

    if(a.size() != b.size()) return 0;

    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            if(a[i].x == b[j].x && a[i].y == b[j].y){
                count++;
                break;
            }
        }
    }

    if(count == a.size()) return a.size();
    else return 0;
}

int solution(vector<vector<int> > game_board, vector<vector<int> > table) {
    vector<vector<bool> > board;
    vector<vector<bool> > puzzles;
    for(int i = 0; i < table.size(); i++){
        vector<bool> v1;
        vector<bool> v2;
        vector<bool> v3;
        for(int j = 0; j < table[i].size(); j++){
            v1.push_back(!game_board[i][j]);
            v2.push_back(table[i][j]);
            v3.push_back(false);
        }
        board.push_back(v1);
        puzzles.push_back(v2);
        check.push_back(v3);
    }

    for(int i = 0; i < puzzles.size(); i++)
        for(int j = 0; j < puzzles[i].size(); j++)
            if(!check[i][j] && puzzles[i][j]) puzzleList.push_back(getPuzzle(i,j,puzzles));

    int count = 4;
    int answer = 0;
    fill(check.begin(),check.end(),vector<bool>(check.size(),false));
    
    while(count--){
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board.size(); j++)
                if(board[i][j] && !check[i][j]) 
                    emptyList.push_back(getPuzzle(i,j,board));

        for(int i = 0; i < puzzleList.size(); i++){
            for(int j = 0; j < emptyList.size(); j++){
                int val = comparePuzzle(puzzleList[i],emptyList[j]);
                if(val != 0) {
                    answer += val;
                    board = fillBoard(emptyList[j],board);
                    puzzleList.erase(puzzleList.begin()+i);
                    emptyList.erase(emptyList.begin()+j);
                    i--;
                    break;
                }
            }
        }
        board = rotateOnce(board);

        fill(check.begin(),check.end(),vector<bool>(check.size(),false));
    }
    return answer;
}

 

 

정답!

---

 
 
참고한 게시글

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