[백준] 2933 - 미네랄

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

2933번: 미네랄

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
char map[100][100];

int getLeft(int i) {
	for (int j = 0; j < m; j++) {
		if (map[i][j] == 'x')return j;
	}
	return -1;
}

int getRight(int i) {
	for (int j = m - 1; j >= 0; j--) {
		if (map[i][j] == 'x')return j;
	}
	return -1;
}

int x[4] = { 0,0,1,-1 };
int y[4] = { 1,-1,0,0 };

void go(int r, int c) {

	map[r][c] = '.';
	int visit[100][100] = { 0, }, visit2[100][100] = { 0, };
	int cnt = 0;
    
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visit[i][j] && map[i][j] == 'x') {
            
				cnt++;
                
				queue<pair<int, int>> q;
				q.push({ i,j });
				visit[i][j] = cnt;
                
				while (!q.empty()) {
                
					int a = q.front().first;
					int b = q.front().second;
					q.pop();
                    
					for (int k = 0; k < 4; k++) {
						int nx = a + x[k];
						int ny = b + y[k];
						if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visit[nx][ny] && map[nx][ny] == 'x') {
							q.push({ nx,ny });
							visit[nx][ny] = cnt;
						}
					}
				}
			}
		}
	}
    
	vector<int> num;
	vector<vector<pair<int, int>>> q2;
    
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'x' && !visit2[i][j]) {
            
				int minH = -1;
                
				queue<pair<int, int>> q;
				q.push({ i,j });
				visit2[i][j] = 1;
				q2.push_back({});
                
				while (!q.empty()) {
                
					int a = q.front().first;
					int b = q.front().second;
					q.pop();

					q2[q2.size() - 1].push_back({ a,b });
					visit2[a][b] = 1;

					for (int k = a; k < n; k++) {
						if (visit[a][b] == visit[k + 1][b])break;
						if (map[k + 1][b] == 'x' || k == n - 1) {
							if (minH == -1 || minH > k - a) {
								minH = k - a;
							}
							break;
						}
					}

					for (int k = 0; k < 4; k++) {
						int nx = a + x[k];
						int ny = b + y[k];
						if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visit2[nx][ny] && map[nx][ny] == 'x') {
							visit2[nx][ny] = 1;
							q.push({ nx,ny });
						}
					}
				}
				if (minH > 0) {
					sort(q2[q2.size() - 1].begin(), q2[q2.size() - 1].end());
					num.push_back(minH);
				}
				else q2.pop_back();
			}
		}
	}

	for (int i = 0; i < q2.size(); i++) {
		while (!q2[i].empty()) {
			int a = q2[i].back().first;
			int b = q2[i].back().second;
			map[a][b] = '.';
			map[a + num[i]][b] = 'x';
			q2[i].pop_back();
		}
	}
}

int main() {

	cin >> n >> m;
    
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
    
	int k; cin >> k;
    
	for (int i = 0; i < k; i++) {
    
		int a; cin >> a;
		int l;
			if (i % 2 == 0) { //왼쪽
			l = getLeft(n - a);
		}
		else {
			l = getRight(n - a);
		}
		if (l != -1) {
			go(n - a, l);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j];
		}
		cout << '\n';
	}
}

 

 

한 번에 맞긴 했지만 코드를 보면 알 수 있듯이 굉장히 지저분하게 짰다.

그래서 일단 내가 짠 코드를 설명하고 다른 분의 블로그를 참고하여 더 나은 방법을 소개하겠다.

 

getLeft(), getRight()

이 부분은 단순히 해당 높이에서 제거할 미네랄의 좌표를 반환하는 함수이다.

 

go()

이 부분은 미네랄을 제거하고 클러스터를 선별한 뒤 움직이는 부분이다.

 

처음 2중 for문은 bfs를 이용해 미네랄이 있는 위치를 모두 클러스터로 선별하고 각각 번호를 새겼다.

 

다음 2중 for문도 bfs를 이용해 클러스터 별로 미네랄을 모두 전수 조사하며 떨어질 수 있는 높이를 구하였다.

높이를 구하는 과정은 for (int k = a; k < n; k++) 이 부분인데,

같은 클러스터 끼리는 볼 필요가 없으므로 continue를 이용해 주었고,

다른 클러스터를 만나거나 땅을 만날 경우 최솟값으로 갱신해주었다.

최솟값으로 갱신한 이유는 최솟값으로 움직여야 같은 클러스터끼리 딱 맞게 이동하기 때문이다.

 

마지막으로 sort를 한 이유는 항상 아래로 떨어지기 때문에, 밑에 있는 것(i가 더 큰 것)을 먼저 수정하면 위에 있는 것(i가 더 작은 것)이 덮어씌울 수 있기 때문이다.

 

그리고 미리 저장해두었던 q2를 이용해 미네랄을 움직이면 끝이다.

 

..

 

다음은 2JINISHAPPY님의 블로그에서 발췌한 내용이다.

핵심은 땅에서 bfs를 돌려준 뒤, 방문하지 않은 x좌표들을 클러스터로 분류하는 것이었다.

이 과정에서 땅에 . 으로 이루어진 한 줄을 추가한다면 편하게 구현할 수 있다.

 

Reference

https://2jinishappy.tistory.com/171