프로그래머스 - [1차] 프렌즈4블록 [C++]

 이 문제는 완전 탐색과 자료구조를 이용해서 풀었다. 일단 이 문제는 배열의 크기가 최대 30 * 30 이고, 구현을 어느 정도 최적화한다면 충분히 완전 탐색으로도 충분히 가능하다고 판단했다. 

 

 

 반복문은 2 * 2가 모두 같은 경우가 없을 경우에만 break 하도록 구현했고, 그 안의 내용은 다음과 같은 수도 코드를 짜서 구현했다.

1. 순회 - 4개 만족하는거 true로 바꿈
2. true의 개수를 세며 answer++ - 해당 블록 ' '로 바꿈
3. 이동 - 위에서 아래로 내려옴 - 여기가 중요
4. 다시 1로 -> 하나도 없을 때까지

 1번과 2번은 단순히 구현하면 되는 부분이라 쉬웠지만, 3번을 구현하는 방법을 떠올리는게 어려웠다. 처음에는 temp라는 벡터를 하나의 x마다 만들어 빈칸이 아닌 부분을 저장하고, 나머지를 빈칸으로 채워 board를 갱신하는 방식으로 구현했는데, 이러면 시간 복잡도가 너무 증가하게 되어 시간 초과가 발생한다. 무조건 이중 for문 안에서 해결해야했고, 우선순위 큐를 이용했다. 

 

 

y가 n-1부터 0까지 돈다
	우선순위큐 선언
	만약 빈칸일 경우
		queue에 자신의 위치를 담도록 푸시
	만약 글자일 경우
		queue가 empty 
			이전까지 빈칸이 없었다 -> continue
		!empty
			top에 있는 것과 스왑
			다시 큐에 집어넣음

  위의 수도코드에서 핵심은 우선순위 큐가 STL에서 기본값으로 최대 힙이라는 것이다. y 좌표가 하단에서 상단으로 가므로, 빈칸의 가장 아랫 부분을 구하기에 최적이었다. 위와 같은 작업을 수행하면, queue에 남아 있는 칸들은 전부 빈칸이므로 굳이 다시 루프를 돌릴 필요도 없었고, 이중 for문 만으로 move 단계를 수행하여 시간을 많이 줄일 수 있었다.

 

 

#include <string>
#include <vector>
#include <queue>

using namespace std;

int dx[] = {0, 1, 0, 1};
int dy[] = {0, 0, 1, 1};

bool isSame(int y, int x, vector<string>& board) {
    if (board[y][x] == ' ') {
        return false;
    }
    
    char first = board[y][x];
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (first != board[ny][nx]) {
            return false;
        }
    }
    
    return true;
}

void makeTrue(int y, int x, vector<vector<bool>>& possible) {
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        possible[ny][nx] = true;
    }
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    while (true) {
        vector<vector<bool>> possible(m, vector<bool>(n, false));
        
        bool same = false;
        // 1. 순회
        for (int y = 0; y < m - 1; y++) {
            for (int x = 0; x < n - 1; x++) {
                // check and make true
                if (isSame(y, x, board)) {
                    same = true;
                    makeTrue(y, x, possible);
                }
            }
        }
        
        if (!same) {
            break;
        }
        
        // 2. count true and make blank
        for (int y = 0; y < m; y++) {
            for (int x = 0; x < n; x++) {
                if (possible[y][x]) {
                    answer++;
                    board[y][x] = ' ';
                }
            }
        }
        
        // 3. move
        for (int x = 0; x < n; x++) {
            priority_queue<int> pq;
            
            for (int y = m - 1; y >= 0; y--) {
                if (board[y][x] == ' ') {
                    pq.push(y);
                }
                else {
                    if (!pq.empty()) {
                        int tempY = pq.top();
                        pq.pop();
                        char temp = board[y][x];
                        board[tempY][x] = temp;
                        board[y][x] = ' ';
                        pq.push(y);
                    }
                }
            }
        }
    }
    
    return answer;
}