[프로그래머스][level4] 블록게임 (C++)

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

코딩테스트 연습 - 블록 게임

 

[난이도] level4
[유형] 구현

[풀이]
N제한이 200으로 여유롭기 때문에 효율적인 알고리즘 보다는 구현능력을 묻는 문제입니다.

아래 코드에서는 map<int,vector<pair<int,int>>> 타입의 block,empt(y) map을 선언하여
block에는 key색상 블록 4개의 좌표를, empty에는 key색상 블록이 직사각형이 되기 위해 채워줘야 하는 좌표 2개를 저장하기로 하였습니다.

block을 구하는 것은 board를 한번 순회하면서 block[board[y][x]].push_back({y,x})와 같이 간단하게 구할 수 있지만,
empty를 구하는 방법은 여러가지가 있을 수 있는데 시간 제한이 여유롭기 때문에 가장 단순한 방법으로 구하였습니다.

각 종류의 블록마다 board를 (0,0) ~ (N-1,N-1) 까지 순회하면서 2x3,3x2 모양을 모든 점에서 확인하는 방식입니다.
예를들어 숫자가 K인 블록의 empty를 찾고 싶을 때, 2x3, 3x2 모양의 모든 직사각형을 확인하면서 K가 적혀있는 점이 4개 있는 곳의 나머지 2개의 점이 K의 empty 블록들입니다.

empty를 구하였다면 while문을 돌면서 지울 수 있는 블록들을 더이상 지울 수 없을때까지 지워주면 됩니다.
empty인 블록 2개 모두 다른 블록의 방해를 받지 않고 보드의 가장 위인 (-1,x)에 도달하면 해당 종류의 블록은 지울 수 있는 것입니다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
int dy1[6]={0,0,0,1,1,1};
int dx1[6]={0,1,2,0,1,2};
int dy2[6]={0,1,2,0,1,2};
int dx2[6]={0,0,0,1,1,1};
int N;
map<int,vector<pair<int,int>>> block,empt;
vector<vector<int>> board;
bool check(int c,vector<pair<int,int>> v){
    for(auto [y,x] : v){
        while(y>=0){
            if(board[y--][x]!=0) return 0;
        }
    }
    for(auto [y,x] : block[c]) board[y][x]=0;
    return 1;
}
int solution(vector<vector<int>> _board) {
    int answer = 0;
    board=_board;
    N=board.size();
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) 
            if(board[i][j]>0) block[board[i][j]].push_back({i,j});

    for(auto [v,mp] : block){
        for(int i=0;i<N-1;i++){
            for(int j=0;j<N-2;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy1[d];
                    int nx=j+dx1[d];
                    if(board[ny][nx]==v) cnt++;
                    else tmp.push_back({ny,nx});
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    for(auto [v,mp] : block){
        for(int i=0;i<N-2;i++){
            for(int j=0;j<N-1;j++){
                vector<pair<int,int>> tmp;
                int cnt=0;
                for(int d=0;d<6;d++){
                    int ny=i+dy2[d];
                    int nx=j+dx2[d];
                    if(board[ny][nx]!=v) tmp.push_back({ny,nx});
                    else cnt++;
                }
                if(cnt==4) empt[v]=tmp;
            }
        }
    }
    bool ok=1;
    vector<bool> erased(201,0);
    while(ok){
        ok=0;
        for(auto [c,v] : empt){
            if(erased[c]) continue;
            if(check(c,v)){
                erased[c]=1;
                ok=1;    
                answer++;
            }
        }
    }
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level4/블록게임.cpp