[C++] 백준 16768번 - Mooyo Mooyo

Mooyo Mooyo == 뿌요뿌요....?

문제가 영어라 해석이 들어가야 한다.

 

문제를 잠시 분석을 한다면,

n X 10의 줄을 입력을 받아서 뿌요뿌요 게임을 실행시켜주면 된다.

먼저 같은 숫자가 k개 이상 연결 되어 있다면 0으로 만들어준다.

이 과정을 dfs로 탐색하고 바꿔준다.

그 후에 중력의 영향을 받아 아래로 블럭들을 아래로 당겨주어야 한다.

아래로 다 당겨주었다면 계속해서 블럭들을 터뜨리고....

이 과정을 계속 반복해주면 된다. 

 

범위 잘못 설정해서 여러번 틀렸다.....

그래프 문제는 진짜 한 시간 이상 걸려서 푸는데

코딩좀 잘 하고 싶어요ㅠㅠ

 

 

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

int n, k;
char table[100][10];
bool visited[100][10];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

bool check_range(int x, int y) {
	if (x >= 0 && x < 10 && y >= 0 && y < n)
		return true;
	else
		return false;
}

int dfs(int y, int x, bool flag) {
	visited[y][x] = true;
	int temp = 1;
	//같은 숫자로 연결되었는지 탐색
	for (int i = 0; i < 4; i++) {
		int my = y + dy[i];
		int mx = x + dx[i];
		if (check_range(mx, my) && !visited[my][mx] && (table[my][mx] == table[y][x])) {
			temp += dfs(my, mx, flag);
		}
	}
	if (flag)
		table[y][x] = '0';
	return temp;
}
//뿌요뿌요 마냥 터트리기
int blast() {
	memset(visited, 0, sizeof(visited));
	bool temp = false;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			if (table[i][j] != '0' && !visited[i][j]) {
				//연결되어 있는 개수가 k 이상일때만 터뜨린다 이때 dfs는 연결 개수만 찾는거
				if (dfs(i, j, false) >= k) {
					memset(visited, 0, sizeof(visited));
					temp = true;
					//이때 0으로 터뜨린다
					dfs(i, j, true);
				}
			}
		}
	}
	if (temp)
		return 1;
	else
		return 0;
}
//이건 처음에 시작하는게 아님 ㅇㅇ
void gravity() {
	for (int j = 0; j < 10; j++) {
		for (int i = n - 1; i >= 0; i--) {
			if (table[i][j] != '0') {
				for (int o = i; i + 1 < n && table[o + 1][j] == '0'; o++) {
					int temp = table[o][j];
					table[o][j] = table[o + 1][j];
					table[o + 1][j] = temp;
				}
			}
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> table[i][j];
		}
	}
	while (blast()) {
		gravity();
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			cout << table[i][j];
		}
		cout << '\n';
	}
	return 0;
}