[프로그래머스/알고리즘] 프렌즈4블록

프렌즈4블록

입풀력 예제

m=4

n=5

board : ["CCBDE","AAADE","AAABF","CCBBF"]

answer : 14

풀이과정

mXn 길이를 처음에 4블록인 것을 확인하기 위해서 높이는 m-1까지 , 폭은 n-1까지 확인해서 해당 위치에 오른쪽 아래쪽, 대각선 위치랑 같은 지 확인을 해서 전부 같으면 블록을 내리면 된다.

4블록이 완성이 되면 visit[n][m] 확인 배열을 이용해서 체크해둔다.

그리고 제거할때마다 visit가 true이면 answer를 증가시키고 위에서 한칸씩 내리는 방법을 이용했다.

내릴 때 1칸씩 내리기 때문에 효율은 굉장히 나쁘지만 구현할 때 매우 편하다. 그리고 내리면서 빈 공간은 0으로 저장시키면서 board가 0일때는 그냥 무시하게 만들어야 했다.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board) {
	int answer = 0;
	bool flag = false;
	while (flag == false) {
		vector<vector<bool>> visit(m, vector<bool>(n));
		flag = true;
		for (int i = 0; i <m-1;i++) {
			for (int j = 0; j < n - 1; j++) {
				if (board[i][j] == 0)
					continue;
				if ((board[i][j] == board[i][j + 1])&& (board[i][j]== board[i + 1][j])&&(board[i][j]== board[i + 1][j + 1])) {
					visit[i][j] = 1;
					visit[i][j+1] = 1;
					visit[i+1][j] = 1;
					visit[i + 1][j + 1] = 1;
					flag = false;
				}
			}
		}

		for (int i = 0; i < m; i++) {	//제거
			for (int j = 0; j < n; j++) {
				if (visit[i][j]==1) {
					answer++;
					for (int k = i-1; k >=0; k--) {
						board[k + 1][j] = board[k][j];
						board[k][j] = 0;
					}
				}
			}
		}

	}

	return answer;
}