[Programmers] Lv2. [1차] 프렌즈4블록 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

이 문제를 풀면서 새로운 교훈을 얻었습니다. 네....

"실력도 없는데, 되지도 않는 방법은 적용하지 말자."

 

 

[첫 시도] 실패

 

처음 구상한 방법으로는 각 열의 루트(Root) 블록 배열을 통해 상하좌우 연결리스트로 관리하는 방법이었습니다. 시각적으로 표현하자면, 대강 다음과 같습니다.

/*
    - 블록은 'O'로 표기
    - '-'과 '|'은 연결 링크를 뜻함
    - []은 배열을 뜻함
*/

[O] [O] [O] [O] [O]
 |   |   |   |   |
 O - O - O - O - O
 |   |   |   |   |
 O - O - O - O - O
 .   .   .   .   .
 .   .   .   .   .
 .   .   .   .   .

 

처음에는 블록 삭제와 윗 블록 슬라이딩에서 오버헤드가 없겠다 하며 좋아 보였습니다. 배열에서 삭제하면 각 원소들만큼 움직여야 하니까요. 그래서 해당 방법을 코드로 작성해 나갔습니다.

그런데 하다보니, 시간이 너무나 오래 걸렸고 보완이 많이 필요하다는 걸 느꼈습니다. 그래서 바로 던져버렸죠...ㅎㅎ

 

 

[두 번째 시도] 성공

 

그래서 그냥 배열 자체에서 구현하기로 했습니다. 왼쪽 맨 위에서 열 방향으로 탐색을 시작할 것이므로, 2 X 2 구간은 현재 위치에서 오른쪽, 아래, 오른쪽 아래 대각선만 확인해주면 되었습니다.

 

1. 2 X 2 블록 체크

using Position = pair<int, int>;
vector<Position> directions { {0, 1}, {1, 0}, {1, 1} };
const char EMPTY = '#';

bool IsCanRemove(const vector<string>& board, int row, int col, int m, int n, char myCharacter) {
	if (board[row][col] == EMPTY)
		return false;

	for (int i = 0; i < directions.size(); i++) {
		int nextRow = row + directions[i].first;
		int nextCol = col + directions[i].second;

		if (nextRow < 0 or nextRow >= m or nextCol < 0 or nextCol >= n)
			return false;

		char symbol = board[nextRow][nextCol];
		if (symbol == EMPTY)
			return false;
		if (board[nextRow][nextCol] != myCharacter)
			return false;
	}
	return true;
}

 

제거 가능한 블록을 찾았다면, 해당 블록 좌표를 별도의 배열에 저장해두면 됩니다.

vector<Position> removeTargets;

for (int row = 0; row < m; row++) {
	for (int col = 0; col < n; col++) {
		if (IsCanRemove(board, row, col, m, n, board[row][col])) {
			removeTargets.emplace_back(row, col);
		}
	}
}

 

이 과정을 제거 가능한 블록이 없을 때까지 반복해야 하므로, do ~ while()문을 사용해 주었습니다.

bool isCanRemove = false;

do {
	isCanRemove = false;
	vector<Position> removeTargets;

	for (int row = 0; row < m; row++) {
		for (int col = 0; col < n; col++) {
			if (IsCanRemove(board, row, col, m, n, board[row][col])) {
				removeTargets.emplace_back(row, col);
				isCanRemove = true;
			}
		}
	}
    
    // 제거 기능
    // 슬라이딩 기능
    
} while (isCanRemove);

 

2. 블록 제거하기

 

이전에 별도로 저장해 놓은 제거 가능한 블록 좌표는 사각형 4칸 중 (0, 0)의 위치이므로, 오른쪽, 아래, 오른쪽 아래 대각선을 차례대로 제거해주면 됩니다. 제거 표시는 '#'으로 하였습니다. 제거되지 않은 블록을 제거할 때에만 카운트를 합니다.

void Remove(vector<string>& board, vector<Position> targets, int& removeCount) {
	for (const auto position : targets) {
		int row = position.first;
		int col = position.second;

		if (board[row][col] != EMPTY) {
			board[row][col] = EMPTY;
			removeCount++;
		}

		for (int i = 0; i < directions.size(); i++) {
			int nextRow = row + directions[i].first;
			int nextCol = col + directions[i].second;

			if (board[nextRow][nextCol] != EMPTY) {
				board[nextRow][nextCol] = EMPTY;
				removeCount++;
			}
		}
	}
}

 

3. 채울 블록 위치와 떨어뜨릴 블록 위치 찾기

 

제일 아래 행(m - 1)부터 올라가면서 빈 공간('#') 좌표를 찾아서 저장합니다. 그리고 그 위 행부터 다시 올라가면서, 아래로 내려올 첫 번째 블록 좌표를 저장합니다.

void SlideToDown(vector<string>& board, int m, int n) {
	for (int col = 0; col < n; col++) {
		Position refillPos(-1, -1);
		Position target(-1, -1);
		int row = m - 1;

		// 채울 공간 찾기
		for (; row >= 0; row--) {
			if (board[row][col] == EMPTY) {
				refillPos = Position(row, col);
				row--;
				break;
			}
		}

		// 제일 먼저 내려올 애 찾기
		for (; row >= 0; row--) {
			if (board[row][col] != EMPTY) {
				target = Position(row, col);
				break;
			}
		}

		bool isExistTarget = (target.first != -1) and (target.second != -1);
		bool isExistRefillPlace = (refillPos.first != -1) and (refillPos.second != -1);

		if (isExistTarget and isExistRefillPlace)
			Replace(board, target, refillPos);
	}
}

 

두 좌표를 찾았다면, 아까 찾은 아래로 내려올 첫 번째 블록(target) 위치부터 0번 행까지 쭉 올라가면서 채울 공간 위치(refillPos)로 내려줍니다. 내린 후, target 블록은 빈 공간('#')으로 표시하고, target과 refillPos의 행을 -1씩 해줍니다.

그리고 윗 행으로 올라가서 다시 반복해줍니다. 만약, target이 빈 공간이라면 그 윗 행으로 그냥 넘어갑니다.

void Replace(vector<string>& board, Position target, Position refillPos) {
	if (target.first < 0)
		return;

	int targetRow = target.first, targetCol = target.second;
	int refillRow = refillPos.first, refillCol = refillPos.second;
	Position newRefill = refillPos;

	if (board[targetRow][targetCol] != EMPTY) {
		board[refillRow][refillCol] = board[targetRow][targetCol];
		board[targetRow][targetCol] = EMPTY;
		newRefill = Position(refillRow - 1, refillCol);
	}

	Replace(board, Position(targetRow - 1, targetCol), newRefill);
}

 

이렇게 반복해주면 됩니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
using namespace std;
using Position = pair<int, int>;
vector<Position> directions { {0, 1}, {1, 0}, {1, 1} };
const char EMPTY = '#';

bool IsCanRemove(const vector<string>& board, int row, int col, int m, int n, char myCharacter) {
	if (board[row][col] == EMPTY)
		return false;

	for (int i = 0; i < directions.size(); i++) {
		int nextRow = row + directions[i].first;
		int nextCol = col + directions[i].second;

		if (nextRow < 0 or nextRow >= m or nextCol < 0 or nextCol >= n)
			return false;

		char symbol = board[nextRow][nextCol];

		if (symbol == EMPTY)
			return false;
		if (board[nextRow][nextCol] != myCharacter)
			return false;
	}
    
	return true;
}

void Remove(vector<string>& board, vector<Position> targets, int& removeCount) {
	for (const auto position : targets) {
		int row = position.first;
		int col = position.second;

		if (board[row][col] != EMPTY) {
			board[row][col] = EMPTY;
			removeCount++;
		}

		for (int i = 0; i < directions.size(); i++) {
			int nextRow = row + directions[i].first;
			int nextCol = col + directions[i].second;

			if (board[nextRow][nextCol] != EMPTY) {
				board[nextRow][nextCol] = EMPTY;
				removeCount++;
			}
		}
	}
}


void Replace(vector<string>& board, Position target, Position refillPos) {
	if (target.first < 0)
		return;

	int targetRow = target.first, targetCol = target.second;
	int refillRow = refillPos.first, refillCol = refillPos.second;
	Position newRefill = refillPos;

	if (board[targetRow][targetCol] != EMPTY) {
		board[refillRow][refillCol] = board[targetRow][targetCol];
		board[targetRow][targetCol] = EMPTY;
		newRefill = Position(refillRow - 1, refillCol);
	}

	Replace(board, Position(targetRow - 1, targetCol), newRefill);
}


void SlideToDown(vector<string>& board, int m, int n) {
	for (int col = 0; col < n; col++) {
		Position refillPos(-1, -1);
		Position target(-1, -1);
		int row = m - 1;

		// 채울 공간 찾기
		for (; row >= 0; row--) {
			if (board[row][col] == EMPTY) {
				refillPos = Position(row, col);
				row--;
				break;
			}
		}

		// 제일 먼저 내려올 애 찾기
		for (; row >= 0; row--) {
			if (board[row][col] != EMPTY) {
				target = Position(row, col);
				break;
			}
		}

		bool isExistTarget = (target.first != -1) and (target.second != -1);
		bool isExistRefillPlace = (refillPos.first != -1) and (refillPos.second != -1);

		if (isExistTarget and isExistRefillPlace)
			Replace(board, target, refillPos);
	}
}

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

	do {
		isCanRemove = false;
		vector<Position> removeTargets;

		for (int row = 0; row < m; row++) {
			for (int col = 0; col < n; col++) {
				if (IsCanRemove(board, row, col, m, n, board[row][col])) {
					removeTargets.emplace_back(row, col);
					isCanRemove = true;
				}
			}
		}

		Remove(board, removeTargets, answer);
		SlideToDown(board, m, n);
	} while (isCanRemove);
	return answer;
}