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

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

레벨 3이라 생각없이 덤볐다가 피봤다. 내가 겪은 문제 중 구현이 젤 빡센듯하다;
어렵거나 알고리즘을 요구하지않고, 순수 구현만으로 2시간 넘게 풀었다...
심지어 정답을 구하는 과정에서 마지막에 인덱스를 잘못줘서 1시간 넘게 개삽질했다;

푼 과정은 다음과 같다.
1. game_board, table에서 먼저 bfs를 돌아서 block들을 추출한다.

• 문제에서 주어진 조건이 bfs를 쉽게 만드니 금방 가능하다.
• 추출 뒤 0, 0을 기준으로 모두 shift 해준다.
• 이는 기준점을 0, 0으로 통일시켜서 game_board와 table의 block들을 비교할 때, row, col을 신경쓰지 않고 순수 block 끼리만 비교하기위해서다.

2. table에서 추출된 block들은 rotate를 시켜준다.

• 시계방향으로 0도, 90도, 180도, 270도 회전시켜준다.
• 이 때, 기준점이 계속 바뀌는데 돌린 뒤 0행 혹은 0열에 1이 무조건 오도록 shift 해준다.
• 만약 0행 혹은 0열에 1이 없다면 기준점이 0, 0이 아니라는 의미이기 때문에 추후 비교 과정에서 오류를 발생시킬 수 있다.
  예시는 다음 그림과 같다.
  

3. 이후 주어진 table block과 game_board_block을 돌면서 비교한다. 만약 같으면 그 블락크기만큼 answer을 증가시킨다.

• 이 과정에서 game_board_block의 index를 줘서 answer를 추가해야했는데, table_block의 index를 줘서 계속 틀렸다...

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

using namespace std;


int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };

int visit_block[3000];

int n;
vector<vector<vector<vector<int>>>> block_board;
vector<vector<int>> table;
int table_visit[100][100];
void find_block(int row, int col)
{
    vector<vector<int>> r;
    queue<vector<int>> q;
    r.push_back( {row, col} );
    q.push( {row, col} );
    table_visit[row][col] = 1;
    while(1) {
        if(q.empty())
            break;
        vector<int> pos = q.front(); q.pop();
        vector<int> npos(2, 0);
        for(int i=0;i<4;i++) {
            npos[0] = pos[0] + rowDir[i];
            npos[1] = pos[1] + colDir[i];
            if(npos[0] < 0 || npos[0] > n - 1)
                continue;
            if(npos[1] < 0 || npos[1] > n - 1)
                continue;
            if(table[npos[0]][npos[1]] == 0)
                continue;
            if(table_visit[npos[0]][npos[1]] == 1)
                continue;
            r.push_back(npos);
            q.push(npos);
            table_visit[npos[0]][npos[1]] = 1;
        }
    }
    int row_min = INT_MAX, col_min = INT_MAX;
    int row_max = -1, col_max = -1;
    for(int i=0;i<r.size();i++) {
        row_min = min(r[i][0], row_min);
        row_max = max(r[i][0], row_max);
        col_min = min(r[i][1], col_min);
        col_max = max(r[i][1], col_max);
    }
    int s = max(row_max - row_min + 1, col_max - col_min + 1);
    vector<vector<int>> block(s, vector<int>(s, 0));
    for(int i=0;i<r.size();i++) 
        block[r[i][0] - row_min][r[i][1] - col_min] = 1;
    
    vector<vector<vector<int>>> tmp(4, vector<vector<int>>(s, vector<int>(s, 0)));
    for(int i=0;i<s;i++) 
        for(int j=0;j<s;j++) 
            tmp[0][i][j] = block[i][j];
            
    for(int iter=1;iter<4;iter++) 
        for(int i=0;i<s;i++) 
            for(int j=0;j<s;j++) 
                tmp[iter][j][s-1-i] = tmp[iter-1][i][j];
    
    vector<vector<vector<int>>> blocks(4, vector<vector<int>>(s, vector<int>(s, 0)));
    for(int iter=0;iter<4;iter++) {
        int empty_row_start = 0;
        for(int i=0;i<s;i++) {
            bool is_empty = true;
            for(int j=0;j<s;j++) {
                if(tmp[iter][i][j] == 1) {
                    is_empty = false;
                    break;
                }
            }
            empty_row_start = i;
            if(!is_empty)
                break;
        }
        int empty_col_start = 0;
        for(int i=0;i<s;i++) {
            bool is_empty = true;
            for(int j=0;j<s;j++) {
                if(tmp[iter][j][i] == 1) {
                    is_empty = false;
                    break;
                }
            }
            empty_col_start = i;
            if(!is_empty)
                break;
        }
        for(int i=empty_row_start;i<s;i++) 
            for(int j=empty_col_start;j<s;j++) 
                blocks[iter][i-empty_row_start][j-empty_col_start] = tmp[iter][i][j];
    }
    block_board.push_back(blocks);
}

int g;
vector<vector<vector<int>>> game_board_block;
vector<vector<int>> game_board;
int game_board_visit[100][100];
void find_board_block(int row, int col)
{
    vector<vector<int>> r;
    queue<vector<int>> q;
    r.push_back( {row, col} );
    q.push( {row, col} );
    game_board_visit[row][col] = 1;
    while(1) {
        if(q.empty())
            break;
        vector<int> pos = q.front(); q.pop();
        vector<int> npos(2, 0);
        for(int i=0;i<4;i++) {
            npos[0] = pos[0] + rowDir[i];
            npos[1] = pos[1] + colDir[i];
            if(npos[0] < 0 || npos[0] > g - 1)
                continue;
            if(npos[1] < 0 || npos[1] > g - 1)
                continue;
            if(game_board[npos[0]][npos[1]] == 1)
                continue;
            if(game_board_visit[npos[0]][npos[1]] == 1)
                continue;
            r.push_back(npos);
            q.push(npos);
            game_board_visit[npos[0]][npos[1]] = 1;
        }
    }
    int row_min = INT_MAX, col_min = INT_MAX;
    int row_max = -1, col_max = -1;
    for(int i=0;i<r.size();i++) {
        row_min = min(r[i][0], row_min);
        row_max = max(r[i][0], row_max);
        col_min = min(r[i][1], col_min);
        col_max = max(r[i][1], col_max);
    }
    int s = max(row_max - row_min + 1, col_max - col_min + 1);
    vector<vector<int>> block(s, vector<int>(s, 0));
    for(int i=0;i<r.size();i++) 
        block[r[i][0] - row_min][r[i][1] - col_min] = 1;
    game_board_block.push_back(block);
}
bool is_same_block(vector<vector<int>> table_b, vector<vector<int>> game_b)
{
    int table_size = table_b.size();
    int game_size = game_b.size();
    if(table_size != game_size)
        return false;
    
    for(int i=0;i<game_size;i++) 
        for(int j=0;j<game_size;j++) 
            if(table_b[i][j] != game_b[i][j])
                return false;

    return true;
}
int answer_plus(int idx)
{
    int result = 0;
    vector<vector<int>> r = game_board_block[idx];
    for(int i=0;i<r.size();i++) 
        for(int j=0;j<r[i].size();j++) 
            result += r[i][j];
    
    return result;
}
int solution(vector<vector<int>> game_board__, vector<vector<int>> table__) {
    int answer = 0;
    game_board = game_board__;
    table = table__;
    
    n = table.size();
    for(int i=0;i<table.size();i++) 
        for(int j=0;j<table[i].size();j++) 
            if(table_visit[i][j] == 0 && table[i][j] == 1) 
                find_block(i, j);
            
    g = game_board.size();
    for(int i=0;i<game_board.size();i++) 
        for(int j=0;j<game_board[i].size();j++) 
            if(game_board_visit[i][j] == 0 && game_board[i][j] == 0) 
                find_board_block(i, j);

    for(int game_block_cnt=0; game_block_cnt<game_board_block.size(); game_block_cnt++) {
        bool is_fin = false;
        for(int block=0; block<block_board.size(); block++) {
            if(visit_block[block] == 1) 
                continue;
            for(int rotate=0; rotate<4; rotate++) {
                if(is_same_block(block_board[block][rotate], game_board_block[game_block_cnt])) {
                    visit_block[block] = 1;
                    answer += answer_plus(game_block_cnt);
                    is_fin = true;
                    break;
                }
            }
            if(is_fin)
                break;
        }
    }
    return answer;
}