[개쉬운 풀이] 백준 2933 미네랄 (4일차)

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

 

문제

 

생각

1. 천천히 구현하면 된다.

2. 왼쪽, 오른쪽을 구분해서 미네랄을 탐지해야한다.

3. 행이 아래부터 0,0이기 때문에 구현할때는 평소 구현할때 Row를 뒤집어서 생각해야한다.

4. 미네랄을 파괴시키고 그 주변 4칸을 클러스터 판별하자.

5. 클러스터는 1개만 떨어진다.

6. 클러스터에 해당하는 정보들을 저장해야한다.

7. 클러스터가 떨어질때 ㄷ 자 모양같은 경우 위 클러스터와 아래클러스터가 떨어질 수 있는 범위가 다를 수 있다. //좋은 예시

8. 따라서 모든 클러스터 정보에 대해서 떨어지는 경우를 구한 뒤, 최소값을 찾아서 떨어뜨려야한다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 101;

int R, C;
char map[MAX][MAX];
bool isVisited[MAX][MAX];
int N;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
vector<int> sticks;
vector<pair<int,int>> cluster;

void input(){
	cin >> R >> C;
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			cin >> map[i][j];
		}
	}

	cin >> N;
	sticks = vector<int> (N);
	for(int i = 0; i < N; i++){
		cin >> sticks[i];
		sticks[i] = R - sticks[i] + 1;
	}
}

bool isOut(int r, int c){
	return r < 1 || c < 1 || r > R || c > C;
}

void init(){
	for(int i = 0; i < MAX; i++){
		for(int j = 0; j < MAX; j++){
			isVisited[i][j] = false;
		}
	}
	cluster.clear();
}

void print(){
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			cout << map[i][j];
		}
		cout << endl;
	}
}

int throwStick(int n, int turn){
	if(turn % 2 == 0){ //왼쪽 -> 오른 (창영 턴)
		for(int c = 1; c <= C; c++){
			if(map[n][c] == '.') continue;
			else if(map[n][c] == 'x'){
				return c;	
			}
		}
	}
	else{	//왼쪽 <- 오른 (상근 턴)
		for(int c = C; c >= 1; c--){
			if(map[n][c] == '.') continue;
			else if(map[n][c] == 'x'){
				return c;
			}
		}
	}
	return -1;
}

void isCluster(int r, int c, bool &check){ //dfs
	if(r == R){
		//cluster가 바닥에 붙어있는 경우 cluster가 아님
		check = false;
		return;
	} 

	isVisited[r][c] = true;
	cluster.push_back({r,c}); //cluster정보 저장
	for(int i = 0; i < 4; i++){
		int nr = r + dx[i];
		int nc = c + dy[i];

		if(!isOut(nr, nc) && !isVisited[nr][nc]){
			if(map[nr][nc] == 'x'){
				isCluster(nr, nc, check);
			}
		}
	}
}

int dropCluster(){
	//모든 클러스터에 대해서 drop 판별하지 않으면 예외가 발생할 수 있음
	int drop = MAX;
	for(int i = 0; i < cluster.size(); i++){
		int x = cluster[i].first;
		int y = cluster[i].second;

		for(int r = x+1; r <= R; r++){ //현재 클러스터보다 아래만 판별하면 됨
			if(map[r][y] == 'x' && !isVisited[r][y]){ 
				drop = min(drop, r-x-1);
				break; //가장 처음 만나는 미네랄이므로 찾으면 break 해야함
			}
			else if(r == R && map[r][y] == '.'){ //바닥
				drop = min(drop, r-x);
			}
		}
	}
		
	return drop;	
}

void dropProcess(int drop){
	//먼저 .로 초기화 한 이후 
	//x로 해야 겹치는 부분이 발생하지 않음
	for(int i = 0; i < cluster.size(); i++){
		int r = cluster[i].first;
		int c = cluster[i].second;
		map[r][c] = '.';
	}
	for(int i = 0; i < cluster.size(); i++){
		int r = cluster[i].first;
		int c = cluster[i].second;
		map[r+drop][c] = 'x';
	}
}

void process(int r, int c){
	map[r][c] = '.'; //맞은 미네랄 파괴

	//맞은 미네랄을 기준으로 주변 cluster판별
	for(int i = 0; i < 4; i++){
		int nr = r + dx[i];
		int nc = c + dy[i];

		if(!isOut(nr, nc) && map[nr][nc] == 'x'){
			init();
			bool check = true;
			isCluster(nr, nc, check);

			if(check){	//cluster가 존재하는 경우
 				int drop = dropCluster(); //얼마나 drop해야하는지 최소값 구함
				dropProcess(drop); //drop
				return;
			}
		}
	}
}

void sol(){
	for(int i = 0; i < sticks.size(); i++){
		int c = throwStick(sticks[i], i);
		
		if(c == -1) continue; //맞은 미네랄이 없음
		else{
			//미네랄이 맞음
			process(sticks[i], c);
		}
	}
}

int main(){

	input();
	sol();
	print();
	return 0;
}

/*
좋은 예시
9 8
........
...xxx..
.xxx....
.x.x.xxx
.x.x...x
.x.xxx.x
.x.....x
.x.....x
.xxx...x
1
7
*/