[프로그래머스] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT)

문제 링크 :  programmers.co.kr/learn/courses/30/lessons/17679

 

시뮬레이션 문제

 

<전체적인 알고리즘>

1. 네 블록이 같은 곳들 전부 터트려준다(check이차원 배열에 표시)

2. 터트려주면 열마다 밑에서 올라오면서 제자리로 떨어뜨려준다.(자신보다 밑에서 터진 개수만큼 떨구면 됨)

3.  1,2 를 반복하다가 더이상 터지는 곳이 없으면 종료.

 

 

<전체 코드>

#include <string>
#include <vector>

using namespace std;


int m=6;
int n=6;
vector<string> board;
bool check[32][32];   //터지는 곳 체크

bool explode()   //4개 같은블록들 터트리기
{
	bool is_exploded = false;
	for (int i = 0; i < m-1; i++)
	{
		for (int j = 0; j < n-1; j++)
		{
			char c = board[i][j]; 
			if (board[i][j] == '0')continue;  //빈 공간이면 스킵
			if (c == board[i][j + 1] && c == board[i + 1][j] && c == board[i + 1][j + 1])
			{
				is_exploded = true;
				check[i][j] = true;
				check[i][j + 1] = true;
				check[i + 1][j] = true;
				check[i + 1][j + 1] = true;
			}
		}
	}
	return is_exploded;
}

void fall()
{
	for (int j = 0; j < n; j++)
	{
		int empty_count = 0;   //터진 개수 카운트
		for (int i = m-1; i >=0; i--)     //열마다 밑에서부터 순차탐색하면서 제자리 찾기
		{
			if (check[i][j] == true)
			{
				empty_count++;  //터진 개수 세기
			}
			else
			{
				board[i + empty_count][j] = board[i][j]; // 자신보다 밑에서 터진 개수만큼 내려가야함
			}		
		}

		for (int i = 0; i < empty_count; i++)
		{
			board[i][j] = '0';  //터진개수만큼 끝에서 부터 빈공간으로 채우기
		}
	}
}

int solution(int m2, int n2, vector<string> boards) {
    board=boards;
    m=m2;
    n=n2;
    fill(&check[0][0],&check[29][30],0);
    
    while (1)
	{		
		bool is_exploded=explode();  //터지는 부분 check하기
		if (!is_exploded)break;   //터진블록들 없으면 탈출

		fall();       //블록들 떨어뜨리기
        fill(&check[0][0], &check[29][30], 0);
	}

	int count = 0;
	for (int i = 0; i < m; i++)   //빈 공간들 갯수 구하기(빈공간 = 터진 개수)
	{
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == '0')count++;  
		}
	}   
    return count;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.