[프로그래머스] 프렌즈 4블록

✔️ 문제 링크

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

프로그래머스

---

✔️ 문제 이해

1.  문제 조건대로 구현하면된다. 2x2 공간에 같은 모양의 블록이 있으면 터뜨리고, 빈공간은 위에서 아래로 채운다.

---

✔️ 설계

- 2x2 공간에 같은 모양의 블록이 있으면 check 배열에 체크해둔다. 

---

✔️ 문제 회고

- 2x2 위치에 같은 모양의 블록이 있는지 확인하는 작업을 재귀로 구현했더니 시간초과가 났고, 구현이 복잡해졌고, 오답이 나왔다. 

- 2x2 위치라고 명시되어 있으므로, 굳이 재귀로 확인하지 않고 2x2에 해당하는 4개의 블록을 순차적으로 확인하면 간단해졌다. 범위를 0~m-1, 0~n-1로 제한하여 배열 범위 초과가 발생하지 않도록 하는 좋은 아이디어가 있었다.

---

👨🏻‍💻 소스 코드 

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

const int dx[] = { 0, 0,1,1 }, dy[] = { 0,1,0,1 };
vector<string> g_board;

void fall(int m, int n) {
	for (int col = 0; col < n; col++) {
		for (int row = m - 1; row >= 0; row--) {
			if (g_board[row][col] != 'x') {
				for (int k = m - 1; k >= row; k--) {
					if (g_board[k][col] == 'x') {
						swap(g_board[row][col], g_board[k][col]);
						break;
					}
				}
			}
		}
	}
}

int solution(int m, int n, vector<string> board) {
	int answer = 0;
	bool flag;
	bool check[30][30];
	g_board = board;

	while (1) {
		flag = false;
		memset(check, false, sizeof(check));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {

				if (i + 1 >= m || j + 1 >= n) continue;
				int cnt = 0;
				for (int r = i; r < i + 2; r++) {
					for (int c = j; c < j + 2; c++) {
						if (g_board[r][c] != 'x') {
							if (g_board[r][c] == g_board[i][j]) cnt++;
						}
					}
				}

				if (cnt == 4) {
					flag = true;
					for (int r = i; r < i + 2; r++) {
						for (int c = j; c < j + 2; c++) {
							if (g_board[r][c] != 'x') {
								check[r][c] = true;
							}
						}
					}
				}
			}
		}

		if (!flag) return answer;

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (check[i][j] && g_board[i][j] != 'x') {
					g_board[i][j] = 'x';
					answer++;
				}
			}
		}
		fall(m, n);
	}

	return answer;
}

👨🏻‍💻 개선된 소스 코드 

#include <string>
#include <vector>

using namespace std;

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

	while (1) {
		flag = false;
		bool check[30][30] = { false };

		// m-1, n-1 까지만 확인해도 된다. 이러면 배열 범위 초과에 대한 예외처리 코드 작성하지 않아도 된다.
		for (int i = 0; i < m - 1; i++) { 
			for (int j = 0; j < n - 1; j++) {

				// 예외처리 : 비어있는 공간.
				if (board[i][j] == 0) continue;

				// 2x2 공간에 모두 같은 블록이 있는지 확인한다.
				if ((board[i][j] == board[i + 1][j])
					&& (board[i][j] == board[i][j + 1])
					&& (board[i][j] == board[i + 1][j + 1])) {
					check[i][j] = true;
					check[i + 1][j] = true;
					check[i][j + 1] = true;
					check[i + 1][j + 1] = true;
					flag = true; // flag set : 터뜨릴 수 있는 블록이 존재한다.
				}

			}
		}

		if (!flag) break; // 터뜨릴 수 있는 블록이 없을 경우 탈출

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (check[i][j]) {
					answer++; // 블록 개수 체크 

					// 터뜨릴 수 있는 블록 바로 위부터 맨 위까지 순차적으로 아래로 하나씩 옮긴다.
					for (int k = i - 1; k >= 0; k--) {
						board[k + 1][j] = board[k][j];
						board[k][j] = 0;
					}
				}
			}
		}
	}

	return answer;
}