[백준 2933, 18500] 미네랄, 미네랄2

뭐가 다른지 모르겠음 사실상 같은 문제인듯... ? ㅋㅋㅋㅋㅋ

미네랄 AC받았다면 미네랄2도 넣어보기를 추천~

2933 미네랄

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

2933번: 미네랄

 

18500 미네랄

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

18500번: 미네랄 2

#include <cstdio>
#include <cstring>
#include <vector>
int R, C;
int N;
char board[100 + 2][100 + 2];
char tmp[100 + 2][100 + 2];
int CMD[100 + 2];	// 막대 던진 높이

int visited[100 + 2][100 + 2];

struct _st
{
	int x, y;
};
std::vector<_st> V;


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int h = 0;
		scanf("%d", &h);
		CMD[i] = R + 1 - h;	
	}
}

void left_side(int h)
{
	for (int j = 1; j <= C; j++) {
		if (board[h][j] == 'x') {
			board[h][j] = '.';
			return;
		}
	}
}

void right_side(int h)
{
	for (int j = C; j >= 1; j--) {
		if (board[h][j] == 'x') {
			board[h][j] = '.';
			return;
		}
	}
}


void DFS(int x, int y)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	visited[x][y] = 1;
	V.push_back({ x, y });

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];
		if (visited[nx][ny]) continue;
		if (board[nx][ny] == 'x') DFS(nx, ny);
	}
}


void pull_down()
{
	int offset = 1;
	int size = V.size();
	int block = 0;

	while (1) {
		for (_st v : V) {
			int nx = v.x + offset;
			int ny = v.y;
			if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
			if (tmp[nx][ny] == 'x') continue;
			block++;
		}
		if (block == size) {
			block = 0;
			offset++;
			continue;
		}
		else break;
	}

	offset -= 1;
	// 진짜 놓기 
	for (_st v : V) {
		int nx = v.x + offset;
		int ny = v.y;
		tmp[nx][ny] = 'x';
	}
}


void gravity()
{
	// tmp init
	for (int i = 1; i <= 101; i++) {
		for (int j = 1; j <= 101; j++) {
			tmp[i][j] = '.';
		}
	}

	memset(visited, 0, sizeof(visited));

	for (int i = R; i >= 1; i--) {
		for (int j = 1; j <= C; j++) {
			if (visited[i][j]) continue;
			if (board[i][j] == 'x') {
				if (i == R) {	// 바닥에 붙어있는 클러스터
					V.clear();
					DFS(i, j);
					for (_st v : V) {
						tmp[v.x][v.y] = 'x';
					}
				}
				else {	// 공중에 떠있는 클러스터
					V.clear();
					DFS(i, j);
					pull_down();
				}
			}
		}
	}
	memcpy(board, tmp, sizeof(tmp));
}



void simul()
{
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) left_side(CMD[i]);
		else right_side(CMD[i]);
		gravity();
	}
}



void output()
{
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			printf("%c", board[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	input();
	simul();
	output();
	return 0;
}

질문 게시판 보니까 9% 틀렸습니다 이유가 굉장히 다채롭던데... 나 같은 경우에는 로직이 틀렸었다. 

중력 작용하는 과정에서 바닥 부분부터 공중에 뜬 클러스터를 위치시켜보고, 만약 영역을 벗어나거나 원래 있던 다른 클러스터와 겹치지 않으면 그 자리에 위치하도록 코드를 짰다. 

이렇게 구현하면 안되는 이유는 다음과 같은 반례 때문이다. 

 

>> input
7 5 
..... 
.xxx. 
.x... 
xx.xx 
x...x 
x...x 
x...x 
1 
4 
    
>> right output
.....
.....
.xxx.
.x.xx
xx..x
x...x
x...x

>> wrong output	
.....
.....
.....
...xx
xxxxx
xx..x
xx..x

공중에 뜬 클러스터가 다른 클러스터로 인해 중간에 걸려야 하는데 빈 공간으로 쏙 들어오는 불상사가 발생하는 것이다..... 

이 부분을 해결하니까 AC 받을 수 있었다... (위 반례는 질문 게시판에도 남겨 놓았다 ㅎㅎ 디버깅 할 때 게시판의 다른 반례는 다 맞아서 맞왜틀 맞왜틀 하고 있었기 때문 ㅠ)

 

그리고 풀면서 한 가지 더 놓쳤던 부분은, 한 번 막대기를 던질 때 마다 중력이 작용하는데 막대기를 다 던지고 나서 중력이 작용하는 것으로 착각했다는 것이다. 

 

문제 좀 잘 읽어야지.... 

---

++22.11.10 Flood_Fill 시 BFS로 탐색한 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
int R, C;	// 최대 100 * 100
char board[100 + 2][100 + 2];
char tmp[100 + 2][100 + 2];

int N;
int CMD[100 + 2];	// 막대를 던진 횟수 최대 100
					// 0~짝수 왼쪽, 홀수 오른쪽


struct _st
{
	int x, y;
};
std::vector<_st> V;
std::queue<_st> Q;
int visited[100 + 2][100 + 2];



void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 1; i <= R; i++) {
		scanf("%s", &board[i][1]);
	}
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int h = 0; 
		scanf("%d", &h);
		CMD[i] = R - h + 1;
	}
}

void throw_left_side(int height)
{
	for (int j = 1; j <= C; j++) {
		if (board[height][j] == 'x') {
			board[height][j] = '.';
			return;
		}
	}
}

void throw_right_side(int height)
{
	for (int j = C; j >= 1; j--) {
		if (board[height][j] == 'x') {
			board[height][j] = '.';
			return;
		}
	}
}

void BFS(int x, int y)
{
	// dir
	int dir_x[4] = { 0, 0 ,1 , -1 };
	int dir_y[4] = { 1, -1, 0, 0 };
	
	// init
	Q = {};
	V.clear();

	Q.push({ x, y });
	visited[x][y] = 1;
	V.push_back({ x, y });

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
			if (board[nx][ny] == '.') continue;
			if (visited[nx][ny]) continue;
			Q.push({ nx , ny });
			visited[nx][ny] = 1;
			V.push_back({ nx, ny });
		}
	}
}

void pull_down()
{
	int offset = 1;
	bool set = false;

	while (1) {
		for (_st v : V) {
			int px = v.x + offset;
			int py = v.y;

			if (tmp[px][py] == 'x' || px > R) {	// 더이상 내리면 안됨 
				set = true;
				break;
			}
		}
		if (set == true) break;
		offset++;
	}

	offset -= 1;
	for (_st v : V) {
		int px = v.x + offset;
		int py = v.y;

		tmp[px][py] = 'x';
	}
}




void gravity()	//Flood_Fill
{
	// init
	memset(visited, 0, sizeof(visited));
	
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			tmp[i][j] = '.';
		}
	}


	for (int i = R; i >= 1; i--) {
		for (int j = 1; j <= C; j++) {
			if (board[i][j] == '.') continue;
			if (visited[i][j]) continue;
			BFS(i, j);
			if (i != R) pull_down();	// 공중에 떠있는 클러스터
			else {
				for (_st v : V) {
					tmp[v.x][v.y] = 'x';
				}
			}
		}
	}
	memcpy(board, tmp, sizeof(tmp));
}




void simulation()
{
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) throw_left_side(CMD[i]);
		else throw_right_side(CMD[i]);
		gravity();
	}
}


void output()
{
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			printf("%c", board[i][j]);
		}
		printf("\n");
	}
}


int main()
{
	input();
	simulation();
	output();
	return 0;
}