(C++) - 프로그래머스(위클리 챌린지) : 3주차

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

코딩테스트 연습 - 3주차

bfs를 이용한 구현이었습니다.

 

 

📕 풀이방법

 크게 해야할 일은 다음과 같습니다. 

 1. game_board에서 빈 곳 찾기, 찾았다면 모양 알아내기 

 2. table에서 빈 곳의 모양과 같은 모양의 블록 찾기, 찾았다면 answer에 블록크기 더해주기

 

📔 풀이과정

 1. game_board 확인하기 :  전체를 한 칸씩 확인합니다. 한 번도 확인한 적 없는 칸이며 비어있을 때 bfs를 수행해서 해당 모양을 구해 emptyBlock이라는 이차원 배열에 저장합니다. 비교의 편의를 위해 가장 왼쪽 위부터 모양을 당겨서 저장해줍니다.

 

 2. 찾은 game_board 빈 칸과 table에 있는 조각 맞춰보기 : table 전체를 한 칸씩 확인합니다. 한 번도 확인한 적 없는 칸이며 1일때 bfs를 수행해 모양을 구합니다. 그 모양을 block이라는 이차원 배열에 정제하여 가장 왼쪽 위부터 저장합니다.

 

 3. emptyBlock 과 block 비교 : 조각은 시계방향으로 4번 돌리면 원래대로 돌아옵니다. 만약 빈 곳과 조각의 모양이 맞지않으면 조각(block)을 시계방향으로 90도 회전합니다. 이를 한 세트로 (비교, 시계방향으로 90도 회전) 4회 실시해 줍니다. 비교해서 맞다면 table에서 그 조각을 없애주고 SUCCESS로 가준 뒤, 조각크기를 answer에 더해줍니다.

 

📔 정답출력

 answer를 반환해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
struct Coord {int r, c; };
vvi gameBoard, table;
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};
int emptyBlock[51][51], block[51][51],n;

void refineBlock(){
    deque <Coord> dq;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(block[i][j]) dq.push_back({i,j}), block[i][j] = 0;
        }
    }

    int minR = 0x3f3f3f3f;
    int minC = 0x3f3f3f3f;
    queue <Coord> tmpQ;

    for(auto d : dq){
        minR = min(minR, d.r);
        minC = min(minC, d.c);
        tmpQ.push(d);
    }

    for(auto &d : dq) d.r -= minR, d.c -= minC;
    for(auto d : dq) block[d.r][d.c] = 1;
}

void rotateBlock(){
    int tmp[51][51] = {0};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            tmp[i][j] = block[n-j-1][i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            block[i][j] = tmp[i][j];
}

bool isSame(){
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(block[i][j] != emptyBlock[i][j]) 
                return false;
    return true;
}

int bfs(int i, int j, int ck[51][51], int option){
    if(!option) memset(emptyBlock,0,sizeof(emptyBlock));
    else memset(block,0,sizeof(block));
    deque <Coord> dq;
    queue <Coord> tmpQ;
    ck[i][j] = 1;
    tmpQ.push({i,j});
    dq.push_front({i,j});
    int area = 1;
    while(!tmpQ.empty()){
        int r = tmpQ.front().r;
        int c = tmpQ.front().c;
        tmpQ.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= n) continue;
            if(!option && gameBoard[nr][nc] || ck[nr][nc]) continue;
            if(option && !table[nr][nc] || ck[nr][nc]) continue;
            ck[nr][nc] = 1;
            dq.push_front({nr,nc});
            tmpQ.push({nr,nc});
            area++;
        }
    }
    
    int minR = 0x3f3f3f3f;
    int minC = 0x3f3f3f3f;

    for(auto d : dq){
        minR = min(minR, d.r);
        minC = min(minC, d.c);
        tmpQ.push(d);
    }
    for(auto &d : dq) d.r -= minR, d.c -= minC;

    if(!option)
        for(auto d : dq)
            emptyBlock[d.r][d.c] = 1;

    else
        for(auto d : dq)
            block[d.r][d.c] = 1;
    
    return area;
}

void delBFS(int i, int j){
    queue <Coord> q;
    q.push({i,j});
    int ck[51][51] = {0};
    ck[i][j] = 1;
    table[i][j] = 0;
    while(!q.empty()){
        int r = q.front().r;
        int c = q.front().c;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= n) continue;
            if(ck[nr][nc] || !table[nr][nc]) continue;
            ck[nr][nc] = 1;
            q.push({nr,nc});
            table[nr][nc] = 0;
        }
    }
}

int solution(vector<vector<int>> game_board, vector<vector<int>> t) {
    gameBoard = game_board;
    table = t;
    int ck[51][51] = {0};
    int ck2[51][51] = {0};
    int answer = 0;
    n = gameBoard.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(ck[i][j] || gameBoard[i][j]) continue;
            
            int area = bfs(i,j,ck,0);
            memset(ck2,0,sizeof(ck2));
            for(int r = 0; r < n; r++){
                for(int c = 0; c < n; c++){
                    if(ck2[r][c] || !table[r][c]) continue;
                    int area2 = bfs(r,c,ck2,1);

                    for(int rot = 0; rot < 4; rot++){
                        if(isSame()){
                            delBFS(r,c);
                            goto SUCCESS;
                        }
                        rotateBlock();
                        refineBlock();
                    }
                }
            }
            continue;
            SUCCESS :
                answer += area;
        }
    }
    return answer;
}