[G4] 백준 11559번 Puyo Puyo C++ 너비 우선 탐색, 시뮬레이션, 구현

리뷰

 

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

게임 뿌요뿌요와 동일한 로직을 시뮬레이션 해서 몇 번 연속으로 연쇄반응 하는지를 구하는 문제

매번 연쇄 반응 시마다 중력을 적용해 줘야 하는 구현도 진행해야 한다.

 

 

전역 변수

• lst : 맵 정보를 입력 받을 문자열 타입 배열
• v : 각 시뮬레이션 단계마다 사용할 방문 배열
• dx, dy : 4방향 탐색을 하기 위한 방향 배열
• n, m : 맵의 세로와 가로 크기를 지정할 변수
• ans : 몇 번 연쇄 반응 했는지를 저장하기 위한 변수
• Pos : 시뮬레이션 시 x, y좌표를 저장하기 위해 정의한 구조체

 

함수

1. getDown

void getDown()

 

중력을 적용하여 공중에 떠있는 뿌요들을 아래로 내리기 위한 함수

1. m개의 열을 탐색하는 반복문을 수행해 준다.
2. 문자 형식의 벡터 stack을 초기화 해준다, 이 벡터를 스택처럼 사용할 예정이다.
3. n개의 행을 탐색하는 반복문을 수행해 준다.
4. 만약 맵 상에서 '.'이 아니라면 스택에 넣어주고 해당 위치를 '.'로 변경해 준다.
5. 정수형 변수 index를 n - 1로 초기화 해준다.
6. 스택이 빌 때까지 index번째행, j열의 값을 스택의 맨 뒤의 값으로 변경해 준 후 스택에서 요소를 빼준다.
7. index는 후위 감소를 하여 행 번호를 계속해서 줄여준다.

 

2. bfs

bool bfs(int sx, int sy, const char& ch)

 

네개 이상의 뿌요가 연결된 경우 해당 뿌요들을 제거해주기 위한 함수

1. 매개변수로 탐색을 시작할 지점의 x, y좌표를 정수형변수 sx, sy로, 색깔을 ch로 입력 받아준다.
2. Pos타입의 큐 q를 초기화 하고 시작 위치 sx, sy를 큐에 삽입해주고, 시작 위치 sx, sy를 방문처리 해준다.
3. Pos타입의 큐 chain을 초기화 하고 시작 위치 sx, sy를 큐에 삽입해 준다.
4. q가 빌 때 까지 반복문을 수행하며 매번 한개씩 요소를 꺼내어 준다.
5. 4방향 탐색을 진행하며 방문처리 되지 않았고, 자신과 같은 색의 뿌요라면 이동을 진행한다.
6. 이동 후에는 방문처리를 해주고 q와 chain에 이동한 좌표를 push해준다.
7. while문이 종료된 후 chain의 size가 4이상이라면 4개의 뿌요가 연결된 상태인 것이다.
8. chain에서 요소를 빼내면서 각각 좌표의 값을 '.'로 변경해 준다.
9. 모든 요소를 빼냈다면 true를 반환하고, chain의 size가 4보다 작다면 false를 반환한다.

 

3. solution

bool solution()

 

몇번의 연쇄 반응이 일어났는지를 체크하기 위한 함수

1. bool타입 변수 flag의 초기값을 false값으로 세팅해 준다.
2. memset메서드를 통해 시뮬레이션에 사용할 방문 배열 v를 0으로 초기화 해준다.
3. 맵을 순회하며 값이 '.'라면 continue해준다.
4. 아니라면 해당 좌표와 뿌요의 색을 bfs함수의 매개변수로 전달하여 호출한다.
5. bfs함수의 리턴 값이 true라면 flag를 true로 변경해 준다.
6. 모든 탐색이 끝난 후에 flag를 리턴해 준다.

 

문제풀이

1. n개의 문자열을 lst배열에 입력 받아준다.
2. solution함수의 반환 값이 false가 나올 때 까지 while루프를 실행해 준다.
3. getDown을 통해 맵 상에 중력을 가해 뿌요들을 내려준다.
4. ans를 증가시킨 뒤 로직을 반복해 준다.
5. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

딱히 없음, 1번만에 AC

 

 

참고 사항

없음

 

 

정답 코드

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

string lst[12];
int v[12][6];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n = 12, m = 6, ans;

struct Pos {
	int x, y;
};

void getDown() {
	for (int j = 0; j < m; ++j) {
		vector<char> stack;
		for (int i = 0; i < n; ++i) {
			if (lst[i][j] != '.') {
				stack.push_back(lst[i][j]);
				lst[i][j] = '.';
			}
		}

		int index = n - 1;
		while (!stack.empty()) {
			lst[index--][j] = stack.back();
			stack.pop_back();
		}
	}
}

bool bfs(int sx, int sy, const char& ch) {
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = 1;
	queue<Pos> chain;
	chain.push({ sx, sy });

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] == ch) {
				v[nx][ny] = 1;
				q.push({ nx, ny });
				chain.push({ nx, ny });
			}
		}
	}
	if (chain.size() >= 4) {
		while (!chain.empty()) {
			Pos pos = chain.front(); chain.pop();
			int cx = pos.x, cy = pos.y;
			lst[cx][cy] = '.';
		}
		return true;
	}
	return false;
}

bool solution() {
	bool flag = 0;
	memset(v, 0, sizeof(v));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (lst[i][j] == '.') continue;
			if (bfs(i, j, lst[i][j])) flag = 1;
		}
	}
	return flag;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < n; ++i) cin >> lst[i];
	while (solution()) {
		getDown();
		ans++;
	}
	cout << ans;
}