[1차]프렌즈4블록(50분)

https://school.programmers.co.kr/learn/courses/30/lessons/17679

구현 아이디어 5분 구현 45분

풀이

구현 문제였다. 어찌어찌 풀었지만 더 좋은 풀이를 찾아 공부해야겠다. 풀면서 map 배열에서 블록이 있는 공간인지 빈 공간인지 검색했어야 하는데 board 배열을 가지고 검색하는 실수를 했다. 고치긴 했지만... 코드를 깔끔하게 짰다면 이런 실수는 금방 눈에 들어왔을 텐데. 공부하자!
풀이를 구글에서 찾아봤지만 다들 나와 얼추 같게 풀었다. 이런 구현 문제는 구현 시간을(45분...) 줄여야겠다.

1. 2*2라고 바로 지우면 겹쳐져 있는 2*2에 대한 처리가 어려워지기 때문에 지울 블록을 vector<pair<int, int>>에 저장한 뒤 지워준다.
2. m-2행의 블록에서 시작해 0인 경우 블록을 내려준다.

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    vector<vector<int>> map(m, vector<int>(n, 0));
    
    for(int i = 0; i < board.size(); ++i)
    {
        for(int j = 0; j < board[i].size(); ++j)
        {
            map[i][j] = board[i][j];
        }
    }
    
    vector<pair<int, int>> erase_board;
    int dr[3] = {0, 1, 1};
    int dc[3] = {1, 1, 0};
    while(true)
    {
        erase_board.clear();
        
        // 1. 2*2 블록 찾기
        for(int i = 0; i <= board.size() - 2; ++i)
        {
            for(int j = 0; j <= board[i].size() - 2; ++j)
            {
                if(map[i][j] == 0) continue;
                
                char c = map[i][j];
                int k = 0;
                for(; k < 3; ++k)
                {
                    if(c != map[i + dr[k]][j + dc[k]])
                        break;
                }
                
                if(k == 3)
                {
                    for(k = 0; k < 3; ++k)
                        erase_board.push_back(make_pair(i + dr[k], j + dc[k]));
                    erase_board.push_back(make_pair(i, j));
                }
            }
        }
        
        // 삭제할 블록이 없으면 break;
        if(erase_board.empty()) break;
        
        // 2. 해당 블록 삭제
        for(int i = 0; i < erase_board.size(); ++i)
        {
            if(map[erase_board[i].first][erase_board[i].second] != 0)
            {
                map[erase_board[i].first][erase_board[i].second] = 0;
                answer++;
            }
        }
        
        // 3. 블록 내리기
        for(int i = m - 2; i >= 0; --i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(map[i][j] == 0) continue;

                int r = i + 1;
                while(r < m && map[r][j] == 0)
                {
                    ++r;
                }                
                char c = map[i][j];
                map[i][j] = 0;
                map[r - 1][j] = c;
            }
        }
    }
        
    return answer;
}