백준 11559 c++ "Puyo Puyo" -PlusUltraCode-

https://www.acmicpc.net/problem/11559

[필자 사고]

구현 문제이다.

구현 문제들의 특징은 여러개의 함수를 만들어서 역할을 분리해야 하는게 keyPoint다

필자는 문제에서 말하는 의도를 잘못 해석하여 계속 해맷었다.

 

일단 사용한 기술은 gravity 그리고 bfs로 같은 구역 점검하기 정도?? 쓴거 같다.

아래는 자세한 코드 해설이다.

 

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 게임 보드(12행 × 6열)를 입력받아 arr 벡터에 저장한다.

• arr 벡터를 12x6 크기로 초기화한다.
• 12개의 문자열을 입력받고, 각 문자열의 문자를 2차원 벡터 arr에 저장한다.

---

3. 좌표가 유효한지 검사 (isInside 함수)

isInside(int sero, int garo) 함수는 주어진 (sero, garo) 좌표가 보드 범위(0 ≤ sero < 12, 0 ≤ garo < 6) 안에 있는지를 검사한다.

---

4. 중력 적용 (Gravity 및 Change_Arr 함수)

블록이 제거된 후에는 중력의 영향을 받아 위에 있는 블록들이 아래로 떨어져야 한다.

• Gravity() 함수
  • 각 열(세로 방향)을 순회하며, 블록이 있는 값을 queue<string>에 저장한다.
  • Change_Arr()를 호출하여 블록들을 아래로 정렬하고, 빈 공간은 "."으로 채운다.
• Change_Arr(queue<string>& tank, int garo) 함수
  • tank 큐에 저장된 블록들을 해당 열의 아래쪽부터 채운다.
  • 남은 위쪽 공간은 "."(빈 공간)으로 채운다.

---

5. BFS를 이용한 블록 탐색 (BFS 함수)

BFS(너비 우선 탐색)를 사용하여 같은 문자로 연결된 블록들을 찾는다.

• 방문 여부를 저장하는 visited 배열을 사용한다.
• 주어진 블록에서 시작하여 상하좌우 4방향을 탐색한다.
• 같은 문자가 연결된 경우 indexTank 벡터에 위치 정보를 저장한다.

---

6. 블록 제거 (checkIndexTank 함수)

• indexTank에 저장된 블록 개수가 4개 이상이면 해당 블록들을 제거한다.
• 제거된 블록들은 "."(빈 공간)으로 표시된다.
• 하나라도 블록이 제거되었다면 true를 반환한다.

---

7. 게임 실행 (Game_Start 함수)

Game_Start() 함수는 게임의 전체 진행을 담당한다.

1. resultFlag를 false로 초기화한다.
2. BFS를 이용해 연결된 블록을 찾고 제거한다.
3. 제거 후 중력을 적용한다.
4. 제거가 발생했으면 resultCount를 증가시키고 다시 반복한다.
5. 더 이상 제거할 블록이 없으면 resultCount를 출력하고 종료한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>

using namespace std;
typedef pair<int, int> Node;

int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };
vector<Node> indexTank;
vector<vector<string>> arr;


void Input() {
	arr.assign(12, vector<string>(6));

	for (int i = 0; i < 12; i++) {
		string str;
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			arr[i][k] = str[k];
		}
	}
}
bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < 12 && garo >= 0 && garo < 6)return true;
	return false;
}

void Change_Arr(queue<string> & tank , int garo) {
	if (tank.empty()) {
		return;
	}
	
	int lastSero = 11 - tank.size();
	
	for (int i = 11; i > lastSero; i--) {
		string nowStr = tank.front();
		tank.pop();
		arr[i][garo] = nowStr;
	}

	for (int i = 0; i <= lastSero; i++) {
		arr[i][garo] = ".";
	}
}
void Gravity() {

	for (int i = 0; i < 6; i++) {
		queue<string> tank;
		for (int k = 11; k >=0; k--) {
			if (arr[k][i] != ".") {
				tank.push(arr[k][i]);
			}
		}
		Change_Arr(tank, i);
	}
}

 void BFS(int sero, int garo, vector<vector<bool>> &visited) {
	 queue<Node> myQueue;
	 myQueue.push({ sero,garo });
	 visited[sero][garo] = true;
	 indexTank.push_back({ sero,garo });

	 while (!myQueue.empty()) {
		 int nowSero = myQueue.front().first;
		 int nowGaro = myQueue.front().second;
		 string nowStr = arr[nowSero][nowGaro];
		 myQueue.pop();

		 for (int i = 0; i < 4; i++) {
			 int nextSero = nowSero + dy[i];
			 int nextGaro = nowGaro + dx[i];
			
			 if (isInside(nextSero, nextGaro)==false)continue;
			 if (visited[nextSero][nextGaro] == true)continue;
			 if (nowStr == arr[nextSero][nextGaro]) {
				 myQueue.push({ nextSero,nextGaro });
				 visited[nextSero][nextGaro] = true;
				 indexTank.push_back({ nextSero,nextGaro });
			 }
		 }
	 }
}

 bool checkIndexTank() {
	 bool flag = false;

	 if (indexTank.size() >= 4) {
		 flag = true;
		 for (int i = 0; i < indexTank.size(); i++) {
			 int sero = indexTank[i].first;
			 int garo = indexTank[i].second;

			 if (arr[sero][garo] == ".") {
				 cout << "fuck";
				 flag = false;
				 break;
			 }
			 arr[sero][garo] = ".";
		 }
	 }

	 vector<Node> newIndexTank;

	 indexTank = newIndexTank;
	 return flag;
 }
 void Print() {
	 cout << '\n';
	 for (int i = 0; i < 12; i++) {
		 for (int k = 0; k < 6; k++) {
			 cout << arr[i][k] << " ";
		 }
		 cout << '\n';
	 }
 }

 bool resultFlag = false;

void Game_Start() {
	int resultCount = 0;
	while (1) {
		resultFlag = false;
		vector<vector<bool>> visited;
		visited.assign(12, vector<bool>(6, false));
		bool flag = false;
		for (int i = 0; i < 12; i++) {
			for (int k = 0; k < 6; k++) {
				if (arr[i][k]=="."||visited[i][k] == true)continue;
				BFS(i, k, visited);
				flag = checkIndexTank();
				if (flag)resultFlag = flag;
			}
		}
		if (resultFlag == true) {
			resultCount++;
			Gravity();
		}
		else {
			cout << resultCount;
			return;
		}
	}
}


int main(void) {
	Input();
	Game_Start();
	
}