[프로그래머스][Level2][C++] 2018 KAKAO BLIND RECRUITMENT[1차] - 프렌즈4블록 - 컴도리돌이

코딩테스트 연습 - [1차] 프렌즈4블록

 

1.  구현 능력을 테스트하기 위한 문제이다. 하지만 필자는 생각보다 오래 걸렸다.
2.  search_2_2 함수 : 2 X 2 배열 기준으로 똑같은 문자열을 갖고 있는 첫번째 x,y 좌표를 queue 에 삽입한다.
3.  delete_same : queue에 존재하는 x,y 좌표를 꺼내서 해당 2 X 2 배열을 ' '로 없애버린다. 
4.  빈 공간을 fill 함수를 통해서 채워준다. 채워줄 때 queue의 사이즈 * 행의 크기 만큼 채워준다. 

반례 체크) ↓↓↓

8, 5, ['HGNHU', 'CRSHV', 'UKHVL', 'MJHQB', 'GSHOT', 'MQMJJ', 'AGJKK', 'QULKK']
> 8


5, 6, ['AAAAAA','BBAATB','BBAATB','JJJTAA','JJJTAA']
> 24


6, 6, ['IIIIOO', 'IIIOOO', 'IIIOOI', 'IOOIII', 'OOOIII', 'OOIIII']
>32

 

int main(void)
{
    cout << solution(4,5,{"CCBDE", "AAADE", "AAABF", "CCBBF"}) << "\n"; // 14
    cout << solution(2,4,{"baab", "baab"}) << "\n"; //4
    cout << solution(6, 6,{"IIIIOO", "IIIOOO", "IIIOOI", "IOOIII", "OOOIII", "OOIIII"}) << "\n"; //32
    cout << solution(8,5,{"HGNHU", "CRSHV", "UKHVL", "MJHQB", "GSHOT", "MQMJJ", "AGJKK", "QULKK"}) << "\n"; //8
}

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

void fill(vector<string>& board)
{
    for(int i=1; i<board.size();i++)
        for(int j=0; j<board[i].size();j++)
            if(board[i][j] == ' ') board[i][j] = board[i-1][j],board[i-1][j] = ' ';
}
queue<pair<int,int>> search_2_2(vector<string>& board)
{
    queue<pair<int,int>> q;
    for(int i=0; i<board.size()-1; i++)
        for(int j=0; j<board[i].size(); j++)
            if(board[i][j] != ' ' and board[i][j] == board[i+1][j] and board[i][j] == board[i][j+1] and board[i][j] == board[i+1][j+1]) q.push({i,j});
    return q;
}

void delete_same(vector<string>& board,queue<pair<int,int>>& q)
{
    int a = q.size();
    while(!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        board[x][y] = ' ',board[x+1][y] = ' ',board[x][y+1] = ' ',board[x+1][y+1] = ' ';
        q.pop();
    }
    for(int i=0; i<a*board.size() ; i++) fill(board);
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    queue<pair<int,int>> q= search_2_2(board);
    while(!q.empty())
    {
        delete_same(board,q);
        q = search_2_2(board);
    }
    for(int i=0; i<board.size(); i++)
        for(int j=0; j<board[i].size(); j++)
            if(board[i][j] == ' ') answer++;
    return answer;
}