[C++로 풀이] 프렌즈 4블록 ⭐⭐

Date: 2021.02.08 Updated: 2021.02.08

카테고리: Programmers

📌 프렌즈 4블록

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    vector<vector<bool>> isSqaure(m, vector<bool>(n, false));
    bool canRemove = false;

    do {
        // 초기화
        for (int i = 0; i < isSqaure.size(); i++)
            fill(isSqaure[i].begin(), isSqaure[i].end(), false);
        canRemove = false;

        // 2x2 정사각형 찾아 기록
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || board[i][j] == '0')
                    continue;
                if (board[i - 1][j - 1] == board[i][j - 1]
                    && board[i - 1][j - 1] == board[i - 1][j]
                    && board[i - 1][j - 1] == board[i][j]) {
                    isSqaure[i][j] = true;
                    isSqaure[i - 1][j] = true;
                    isSqaure[i][j - 1] = true;
                    isSqaure[i - 1][j - 1] = true;
                    canRemove = true;
                }
            }
        }

        // 2x2 정사각형 다 없애기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isSqaure[i][j] == true) {
                    board[i][j] = '0';
                    answer++;
                }
            }
        }

        // 블록 떨어뜨려 빈공간 채우기 (두 번째 행 부터 시작)
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '0') {
                    for (int k = i; k > 0; k--) {
                        if (board[k - 1][j] == '0')
                            break;
                        board[k][j] = board[k - 1][j];
                        board[k - 1][j] = '0';
                    }
                }
            }
        }
    } while (canRemove);

    return answer;
}

do-while 문 (현재의 보드 상태에서 제거할 블록들 찾고 제거하고 땡기는게 한 번의 반복)
- 초기 상태 👉 canRemove는 false, isSqaure의 모든 값들은 false
- 1️⃣ 제거 할 2x2 블록 체크
  - 2x2 블록들이 하나도 없다면 canRemove는 false인 상태로 유지되므로 while문을 종료하고 빠져나온다.
- 2️⃣ 블록들을 본격적으로 제거
- 3️⃣ 블록 떨어뜨려 빈공간 채우기
- do-while 을 사용한 이유는 그냥 단순히 canRemove 초기값은 false로 시작하고 싶은데 반복문 조건은 while (canRemove) 로 쓰고 싶어서였다.

1️⃣ 초기화

        for (int i = 0; i < isSqaure.size(); i++)
            fill(isSqaure[i].begin(), isSqaure[i].end(), false);
        canRemove = false;

현재의 보드 상태에서 제거할 블록들 찾고 제거하고 땡기는게 한 번의 반복.
canRemove는 false.
- 아래 과정에서 제거할 블록을 찾으면 true 로 변경되어 while문을 다음 반복 때 또 돌게 될 것이다.
isSqaure의 모든 값들은 false 로 초기화.
- 이전 while문 반복에서 제거할 블록들이 true 체크 했었는데 제거가 되었으므로 다시 false 로 초기화한다. 변경된 현재의 보드 상태에서 새롭게 제거할 블록들을 찾아야 하므로.

2️⃣ 제거 할 2x2 블록 체크

        // 2x2 정사각형 찾아 기록
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0 || board[i][j] == '0')
                    continue;
                if (board[i - 1][j - 1] == board[i][j - 1]
                    && board[i - 1][j - 1] == board[i - 1][j]
                    && board[i - 1][j - 1] == board[i][j]) {
                    isSqaure[i][j] = true;
                    isSqaure[i - 1][j] = true;
                    isSqaure[i][j - 1] = true;
                    isSqaure[i - 1][j - 1] = true;
                    canRemove = true;
                }
            }
        }

2 x 2 정사각형이 되는지의 기준. 아래와 같은 조건을 만족한다면 board[i][j]는 2 x 2 정사각형의 우하단인 것이다.
- “우하단” 위치가 되는 자리로부터
  - 그래서 첫번째 행(i = 0), 첫번째 열(j = 0)은 체크를 제외한다. (false)
- 1️⃣왼쪽(i,j-1), 2️⃣위쪽(i-1,j), 3️⃣왼쪽위쪽(i-1, j-1) 4️⃣우하단이되는 본인(i,j) 이 4개가 모두 같고
- board[i][j]가 0이 아니라면 (즉 빈공간이 아니라면! 빈 공간은 ‘0’으로 표시하기로 했다.)
board[i][j]는 2 x 2 정사각형의 우하단이 맞다면
- 1️⃣왼쪽(i,j-1), 2️⃣위쪽(i-1,j), 3️⃣왼쪽위쪽(i-1, j-1) 4️⃣우하단이되는 본인(i,j) 자리를 모두 isSqaure에 True 로 체크한다.
  - 추후 isSqaure 원소들이 True 인지를 검사하여 제거할 것.
- canRemove를 True로 하여 다음 while 반복을 또 돌 수 있도록 한다.
  - 제거가 가능했다는 것이므로.. 아무것도 제거되지 못했을때는 이 부분을 만나지 못해 while문 빠져나옴.

FFFFFF
TTFFTT
TTTFTT
FTTTFF
FFFFFF
FFFFFF

예제의 첫 번째 while문 반복에서의 isSqaure 모습

FFFFFF
FFFFFF
FFFFFF
TTFFFF
TTFFFF
FFFFFF

예제의 두 번째 while문 반복에서의 isSqaure 모습

3️⃣ 2x2 블록 제거하기

        // 2x2 정사각형 다 없애기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isSqaure[i][j] == true) {
                    board[i][j] = '0';
                    answer++;
                }
            }
        }

isSqaure True인 자리들은 제거해야할 자리들.
- 제거된 자리므로 board[i][j]를 0으로 변경
- answer를 증가시킨다. (제거한 블록의 수)

4️⃣ 블록 떨어뜨려 빈 공간 채우기

        // 블록 떨어뜨려 빈공간 채우기 (두 번째 행 부터 시작)
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '0') { // 내가 빈 공간이라면
                    for (int k = i; k > 0; k--) {
                        if (board[k - 1][j] == '0')
                            break;
                        board[k][j] = board[k - 1][j]; // 위에 있는 것들 한 칸씩 아래로 땡겨 옴 
                        board[k - 1][j] = '0'; // 땡겨진 것들의 원래 자리는 빈공간으로 만들어주어야 함
                    }
                }
            }
        }

i=1 두번째행부터 검사하여 내가 빈 공간인데 내 위에 있는 것들이 빈 공간이 아니라면 땡겨온다.

이제 빈 공간을 없애고 떨어뜨려서 아래로 땡겨야하는데 정말 주의해야할 점은 바로 위에 것만 땡기는게 아니라 위에 있는 모든 글자들을 전부 아래로 땡겨야 한다는 것이다. 테스트 케이스 5, 10번이 계속 틀려서 애를 먹었는데 문제는 내가 바로 위에 있는 것만 땡겨오는 식으로 처음에 코드를 짰었기 떄문이였다!!

A
A
A
0
A

위와 같은 상태라면 0에서

A
A
0
A
A

바로 위에 것만 땡겨온다면 이렇게 되는게 끝일 것이다.

0
A
A
A
A

이렇게 빈 공간 위에 있는 것들 중 빈 공간 0이 아닌 것들은 모조리 한 칸씩 아래로 땡겨와야 한다. 이 과정을 for (int k = i; k > 0; k–) 안에서 진행함

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️