BOJ - Puyo Puyo(11559)

DFS나 BFS를 이용해서 풀 수 있는 문제입니다. 알고리즘 자체보다 구현하는 것이 어려웠습니다. 한 턴에 한 번 필드를 순회하면서 터트릴 수 있는 뿌요을 모두 터트립니다. 이때 한 턴 안에서 뿌요를 만날 때마다 DFS를 수행합니다. DFS가 수행될 때마다 뿌요의 위치와 개수를 보관하고 있다가, 4개가 넘어가면 뿌요를 터트려서 빈공간으로 변경합니다. 이때 맵에서 하나라도 터트린 경우 다음 턴을 진행합니다.

하나라도 터트린 경우 위에 있는 뿌요를 아래 공간으로 내려줘야 합니다. 이때 Two Pointer를 사용해서 뿌요와 빈 공간의 위치를 찾아서 뿌요를 빈 공간으로 이동시킵니다. 뿌요 포인터는 항상 위로 이동하면서 뿌요를 만났을 때만 빈공간으로 옮기고, 빈공간 포인터는 빈공간이 아닌 경우에만 이동합니다. (시작 위치인 맨 아래에 뿌요가 있는 경우, 뿌요 위치를 빈 공간으로 이동하여 더 이상 빈 공간이 아닌 경우.)

풀이 코드

#include <iostream>
#include <stdio.h>

using namespace std;

int dy[4] = { 1, -1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

#define MAX_ROW 12
#define MAX_COL 6

char map[MAX_ROW][MAX_COL];
int cache_count;

// 순환하면서 연결되는 뿌요 찾기
void dfs(char c, int y, int x, int cache[75][2], bool visited[MAX_ROW][MAX_COL]) {

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= MAX_ROW || nx < 0 || nx >= MAX_COL) continue;
		if (visited[ny][nx] == true) continue;
		if (map[ny][nx] != c) continue;
		else {
			visited[ny][nx] = true;
			cache[cache_count][0] = ny;
			cache[cache_count][1] = nx;
			cache_count++;

			dfs(c, ny, nx, cache, visited);
		}
	}
}

// 전체 순회하면서 뿌요 팝
int pop_puyo() {
	int is_pop = false;
	bool visited[MAX_ROW][MAX_COL] = { 0 };
	int deleted[75][2] = { 0 };
	int deleted_count = 0;

	// 전체 순환
	for (int i = 0; i < MAX_ROW; i++) {
		for (int j = 0; j < MAX_COL; j++) {

			// 빈칸인지 확인
			if (map[i][j] == '.') continue;

			// 삭제된 뿌요 저장
			int cache_list[75][2] = { 0 };
			cache_count = 0;


			// DFS //
			visited[i][j] = true;
			cache_list[cache_count][0] = i;
			cache_list[cache_count][1] = j;
			cache_count++;
			
			dfs(map[i][j], i, j, cache_list, visited);
			/////////


			// 맵에서 제거
			if (cache_count >= 4) {
				for (int k = 0; k < cache_count; k++) {
					int del_y = cache_list[k][0];
					int del_x = cache_list[k][1];
					map[del_y][del_x] = '.';
				}
				is_pop = true;
			}
		}

	}

	return is_pop;
}

void move_puyo() {
	for (int col = 0; col < MAX_COL; col++) {

		// 아래서부터 빈자리 포인터(target_row)와 뿌요 포인터(row)를 이동.
		// 뿌요포인터는 빈자리 포인터보다 항상 앞서야 한다.
		int target_row = MAX_ROW - 1;
		int row = MAX_ROW - 1;
		while (row >= 0) { 
			
			// 둘 다 만족하는 경우 변경
			if (map[row][col] != '.' && map[target_row][col] == '.') {
				map[target_row][col] = map[row][col];
				map[row][col] = '.';
			}

			// 빈자리가 아닌 경우에만 포인터 이동
			// ex) 시작 위치에 뿌요가 있는 경우, 위 단계에서 뿌요가 옮겨온 경우
			if (map[target_row][col] != '.') {
				target_row--;
			}
			
			// 뿌요 찾는 포인터는 매번 이동
			row--;
		}
	}
}
int main() {
	for (int i = 0; i < 12; i++) {
		cin >> map[i];
	}

	int ans = 0;
	while (pop_puyo()) {
		//print_map();
		move_puyo();
		ans++;
	}

	printf("%d", ans);

	return 0;
}