[백준] 11559-Puyo Puyo(C++)

문제링크:https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

테트리스문제입니다. 테트리스를 구현,시뮬레이션 해야하는 문제입니다.

구현 능력을 보여주는데 적합하기 때문에 많은 코딩테스트에서 사용되는 단골 문제이기 때문에 꼭 연습하시길 추천 드립니다. 

 

정말 다양한 방법이 있습니다.  우선 탐색을 통해서 값을 얻어야 하는데 dfs, bfs 모두 상관없습니다. (여기서는 dfs가 코드가 짧고 가독성이 좋습니다.)

 

알고리즘은

• 1. 탐색을 통해서 없애야 하는 인덱스들을 표시한다. 
• 2. 없애야 하는 인덱스들을 없애고, 빈 칸들을 채워넣는다.
• 3. 없애야 하는 인덱스가 없을때 까지 반복한다.

주의 하실점은 연쇄로 터지는 것을 한번의 과정으로 본다는 것입니다. 

 

저는 vector를 사용하였고, dfs 두가지를 이용해서 구현하였습니다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
string val[12];
vector <char> arr[6];

int result = 0;
int x_ar[4] = { 1,-1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
int visited[6][12] = { 0 };

void dfs2(char a, int yy, int xx,int cnt) {
	int sum = cnt;
	
	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == arr[yy][xx] && visited[y][x] == 0) {
			sum++;
			visited[y][x] = sum;
			dfs2(a, y, x,sum );

		}
	}
}

void dfs(char a,int yy,int xx) {
	arr[yy][xx] = '8';
	visited[yy][xx] = -1;
	for (int i = 0; i < 4; i++) {
		int y = yy + y_ar[i];
		int x = xx + x_ar[i];
		if (y >= 0 && y < 6 && x >= 0 && x < 12 && arr[y][x] == a && visited[y][x] != -1) {
			dfs(a, y, x);
		
		}
	}
}

bool solve() {
	bool jud = false;
	
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 12; j++) {
			if (arr[i][j] != '.' ) {
				
				memset(visited, 0, sizeof(visited));
				visited[i][j] = 1;
				dfs2(arr[i][j], i, j, 1);
				
				
				for (int u = 0; u < 6; u++)
					for (int m = 0; m < 12; m++)
						if (visited[u][m] >= 4) {
							char word = arr[u][m];
							dfs(word, u, m);
						}
				
			}
		}
	}
	
	for (int i = 0; i < 6; i++)
		for (int j = 0; j< arr[i].size(); j++)
			if (arr[i][j] == '8') {
				jud = true;
				arr[i].erase(arr[i].begin() + j), j--;
			}
	for (int i = 0; i<6; i++)
		if (arr[i].size() < 12) {
			while (arr[i].size() != 12)
				arr[i].push_back('.');
		}

	return jud;
}

int main() {
	for (int i = 0; i < 12; i++) {
		cin >> val[i];
	}
	
	for (int i = 0; i < 6; i++) 
		for (int j = 11; j >= 0; j--)
			arr[i].push_back(val[j][i]);
	
	while (1) {
		bool jud = false;
		
		jud = solve();
		if (jud == false)
			break;
		result++;	

	}
	cout << result << '\n';
}

 

벡터를 사용하기 위해 입력받은 문자열을 90도 회전해서 벡터에 넣었습니다.

 

dfs2를 호출해서 탐색하며 visited에 이동값들을 표시했습니다. 

이후 dfs를 통해서 visited값이 4인 값과 연결되는 모든 arr값들을 '8'로 바꿔주었습니다.

그 이후 라운드별로 '8' 값들을 모두 지워주고 뒷부분을 '.' 로 채워주는 방식으로 구현했습니다.