알고리즘(C++) / 프로그래머스 level 2 : 프렌즈4블록

level 2 : 프렌즈4블록

https://programmers.co.kr/learn/courses/30/lessons/17679?language=cpp 

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

코드

//프로그래머스 프렌즈4블록
#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int ni[3] = { 0,1,1 }, nj[3] = { 1,0,1 };

//2x2형태인지 확인
bool Block4(int i, int j, vector<string>& board) {
    char c = board[i][j];
    if (c == '*')
        return false;
    for (int k = 0; k < 3; k++) {
        if (board[i + ni[k]][j + nj[k]] != c) {
            return false; //같지 않을 때
        }
    }
    return true;
}

//*로 변경
void Change(int i, int j, vector<string>& board) {
    board[i][j] = '*';
    for (int k = 0; k < 3; k++) {
        board[i + ni[k]][j + nj[k]] = '*';
    }
}

//밑으로 내리기
void Down(int m, int n, vector<string>& board) {
    for (int i = 0; i < n; i++) { // 폭
        for (int j = m - 1; j > 0; j--) { //높이
            if (board[j][i] == '*') {
                for (int k = j - 1; k >= 0; k--) {
                    if (board[k][i] != '*') {
                        board[j][i] = board[k][i];
                        board[k][i] = '*';
                        break;
                    }
                }
            }
        }
    }
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    queue<pair<int, int>> q;
    while(1) {
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (Block4(i, j, board)) {
                    q.emplace(i, j);
                }
            }
        }
        //더이상 지워질 블럭이 없을때
        if (q.empty())
            break;

        while(!q.empty()) {
            Change(q.front().first, q.front().second, board);
            q.pop();
        }

        Down(m, n, board); //떨어지기
    }
    //지워진 블록 개수
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == '*')
                answer++;
        }
    }

    return answer;
}

int main() {
    int m = 6;
    int n = 6;
    vector <string> board = { "TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ" };
    cout << solution(m, n, board) << endl;
    return 0;
}

 

설명

• 2x2블럭을 찾는다. 위치에서 오른쪽 칸, 밑쪽 칸, 오른쪽 밑 대각선 칸이 모두 같은 모양이면 queue에 위치를 push한다.
• queue가 비어있다면 반복문을 빠져나온다.
• queue가 존재하면 그 블럭의 모양을 ' * '로 변경한다. 
• 보드에서 ' * '가 있는 블럭은 위로 보내고 다른 모양을 밑으로 내린다.
• 더 이상 지울 블록이 없으면 반복문을 빠져나와 지워진 블록의 개수를 찾을 수 있다. 

 

고찰

걸린 시간 : 한시간

이번 문제는 한단계씩 지워질 블럭을 찾고 블럭을 지운후 블럭을 떨어뜨리기 단계로 해결해나갔다. 한단계씩 해결해 나가서 큰 어려움은 없었지만 작은 오류들이 있었다. 배열에서 가로와 세로를 혼동하여 오류가 발생했는데 혼동하지 않게 잘 확인해서 문제를 풀어야할 거 같다.