[BOJ 2933 미네랄] 구현 그래프 너비 깊이 우선

문제

 

문제 포인트는 제거 이후 움질일 클러스터를 찾는 부분

문제에서

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.

라는 조건이 주어졌다.

하지만 잘생각해보면 아래와 같은 케이스가 있다.

3 3
xxx
x.x
..x
1
3

.xx
..x
x.x

움직이는 클러스더가 (2,1) 하나이긴 하지만 (1,1)이 제거된 이후에 움직일 가능성이 있는 것은 (2,1)과 (1,2) 클러스터 2개이다. 물론 (1,2) 클러스터가 움직이지 않아서 결론적으로 하나의 클러스터만 움직이지만 그것을 확인하는 과정에선 여러 클러스터가 움직일 가능성이 있다고 판단.

처음엔 이걸 생각못하고 제거되는 위치의 아래는 확인하지 않았다. 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <tuple>

#define MAX_N 101
#define EMPTY '.'
#define MINERAL 'x'
using namespace std;
typedef pair<int, int> pii;

int H, W;
char grid[MAX_N][MAX_N];

bool vis[MAX_N][MAX_N];

vector<pii> vec;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { -1,1,0,0 };

bool InRange(int y, int x) {
	return 1 <= y && y <= H && 1 <= x && x <= W;
}

bool CanGo(int y, int x) {
	return InRange(y, x) && grid[y][x] != EMPTY && !vis[y][x];
}

pii FindTarget(int h, bool left){
	if (left) {
		for (int i = 1; i <= W; i++) 
			if (grid[h][i] != EMPTY)
				return { h,i };
	}
	else {
		for (int i = W; i; i--)
			if (grid[h][i] != EMPTY)
				return{ h,i };
	}
	return { 0,0 };
}

void FindClustter(int y, int x) {
	for (int d = 0; d < 4; d++) {
		int ny = y + dy[d], nx = x + dx[d];
		if (CanGo(ny,nx)){
			vec.push_back({ ny,nx });
			vis[ny][nx] = true;
			FindClustter(ny, nx);
		}
	}
}

bool cmp(pii a, pii b) {
	return a.first > b.first;
}

bool CanMove(int h) {
	for (pii p : vec) {
		if (h + p.first > H ||
			grid[p.first + h][p.second] != EMPTY)
			return false;	
	}
	return true;
}

void Gravity() {
	for (pii p : vec) {
		grid[p.first][p.second] = EMPTY;
	}

	int h = 1;
	while (1) {
		if(!CanMove(h)) break;
		h++;
	}
	h--; 
	for (pii p : vec) {
		grid[p.first + h][p.second] = MINERAL;
	}
}

void Simulate() {
	int t;
	cin >> t;
	bool left = false;
	while (t--) {
		int h;
		cin >> h;
		h = H + 1 - h;
		left ^= true;

		int y, x;
		tie(y,x) =  FindTarget(h, left);

		// 타켓 없으면 다음 턴 진행 
		if (make_pair(y,x) == make_pair(0, 0)) continue;
		grid[y][x] = EMPTY;
		memset(vis, 0, sizeof(vis));

		vec.clear();
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d], nx = x + dx[d];
			if (CanGo(ny, nx)) {
				vec.push_back({ ny,nx });
				vis[ny][nx] = true;
				FindClustter(ny,nx);
				Gravity();
				vec.clear();
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> H >> W;

	for (int i = 1; i <= H; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= W; j++) {
			grid[i][j] = s[j - 1];
		}
	}

	Simulate();

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cout << grid[i][j];
		}
		cout << "\n";
	}
	return 0;
}