[2017_Blind_Kakao] 프렌즈4블록

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

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

 

전에 이런 유형의 문제를 풀어본 적이 있다.

 

시뮬레이션 문제로 올해 3월 A형 역량테스트 시험에 나온 Puyo Puyo라는 문제와 아주 유사하다.

(하지만 카카오가 더 먼저 제출했었으니 카카오가 원조인셈...)

 

아무튼 이런 유형의 문제는 각 모션마다 나눠서 코드를 짜면 된다.(시간복잡도는 각 모션마다 잘 고려해서 짜면됨)

 

-문제 풀이

 

1. 입력을 받는다.(vector<string>으로 입력이 들어옴)

 

2. 입력받은 것을 다루기 쉽게 하기 위해 char형으로 선언한 map에 문자로 넣어준다.

 

3. 한번에 4개 깨질수 있는 것들을 검사한다.

 

4.검사된 것을 바탕으로 깨질 수 있는 블록들을 깨고 answer에 카운트해준다.

 

5. 깨진 블록들을 아래로 내려준다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

char map[31][31];
int check[31][31];

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    
    for (int y = 0; y < m; y++) {
		string s = board[y];
		for (int x = 0; x < n; x++) {
			map[y][x] = s[x];
		}
	}

	bool flag = true;

	while (flag) {
		flag = false;
		
		for (int y = 0; y < m; y++) {
			for (int x = 0; x < n; x++) {
				if (map[y][x] != ' ' && map[y][x] == map[y][x + 1] && map[y][x] == map[y + 1][x] && map[y][x] == map[y + 1][x + 1]) {
					flag = true;
					check[y][x] = 1, check[y][x + 1] = 1, check[y + 1][x] = 1, check[y + 1][x + 1] = 1;
				}
			}
		}

		if (flag) {
			for (int y = 0; y < m; y++) {
				for (int x = 0; x < n; x++) {
					if (check[y][x] == 1) {
						answer += 1;
						check[y][x] = 0;
						map[y][x] = ' ';
					}
				}
			}

			for (int x = 0; x < n; x++) {
				for (int y = m - 2; y >= 0; y--) {
					if (map[y + 1][x] == ' ') {
						
						int cy = y;
						int ny = y + 1;
						while (1) {
							if (map[ny][x] != ' ') break;
							if (ny >= m) break;
							map[ny][x] = map[cy][x];
							map[cy][x] = ' ';
							cy += 1;
							ny += 1;
						}
					}
				}
			}
		}
	}
    
    return answer;
}