[ 백준 2933 ] 미네랄 (C++)

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

2933번: 미네랄

 

내 수준에서는 좀 어려운 문제였다. 단순 구현 문제긴 하지만 머리를 좀 써야 한다. 우선 큰 그림부터 그려보자.

 

문제를 풀기 위한 큰그림과 사용하는 변수는 아래와 같다.

<큰그림>
1. 막대기로 미네랄 캔다
2. 붕 뜬 클러스터가 있으면 내려준다

<사용 변수>
char map[101][101] -> 입력값 저장
int visit[101][101] -> 방문 배열 (dfs에서 사용)
int sticks[100] -> 막대기 배열
int move_row[4] -> 행 이동 배열
int move_col[4] -> 열 이동 배열
int R, C, -> map의 행, 열 크기

 

 

위와 같은 단순한 알고리즘을 구체화시키면 된다. 우선 막대기로 미네랄을 캐는 함수부터 살펴보자. 코드는 아래와 같다. 

 

 

void throw_stick(int row, int flag) {
	int r = R - row + 1; // 던지는 행

	if (flag == 0) {
		// flag = 0 이면 왼쪽에서 던짐
		for (int c = 1; c <= C; c++) {
			if (map[r][c] == 'x') {
				map[r][c] = '.';
				break;
			}
		}
	}
	else if (flag == 1) {
		// flag = 1 이면 오른쪽에서 던짐
		for (int c = C; c >= 1; c--) {
			if (map[r][c] == 'x') {
				map[r][c] = '.';
				break;
			}
		}
	}
}

 

flag는 오른쪽인지 왼쪽인지를 나타낸다. 왼쪽에서 던지면 열을 왼쪽부터 시작하면 되고, 오른쪽에서 던지면 열을 오른쪽부터 시작하면 된다. 최초로 만나는 'x'만 공백으로 처리하고 이후에는 break로 탈출해준다. 문제에서 왼쪽, 오른쪽 번갈아가면서 계속 던진다고 했으므로 flag는 sticks 배열의 인덱스로 판별 가능하다. 짝수 인덱스는 왼쪽, 홀수 인덱스는 오른쪽이다. 

 

다음으로 '붕 뜬 클러스터가 있으면 내려준다'를 구체화시켜보자. 우선 바닥과 붙어 있는 클러스터는 붕 떠 있을수가 없다. 따라서 가장 마지막 행만을 먼저 dfs로 탐색을 진행한 뒤에, 전체 탐색으로 map에서 'x' 이면서 아직 방문하지 않은 칸이 붕 떠 있는 클러스터임을 알 수 있다. 이 클러스터는 따로 저장할 필요가 있다. 그래서 클러스터의 위치를 벡터에 넣어줬다. 함수는 아래와 같다. dfs와 같이 적겠다. dfs는 전형적인 dfs 형태이므로 설명은 생략한다. 

 

void dfs(int x, int y, int flag, vector<pair<int, int>>& v) {
	// flag = 1 이면 벡터에 위치 넣어줌
	visit[x][y] = 1;
	if (flag == 1) v.push_back({ x, y });
	for (int i = 0; i < 4; i++) {
		int xx = x + move_row[i];
		int yy = y + move_col[i];
		if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
			if (!visit[xx][yy] && map[xx][yy] == 'x')
				dfs(xx, yy, flag, v);
		}
	}
}

bool air_cluster(vector<pair<int, int>>& v) {
	memset(visit, 0, sizeof(visit));

	// 1. 바닥 먼저 탐색
	for (int col = 1; col <= C; col++)
		dfs(R, col, 0, v);

	// 2. 이후 전체 탐색 - 클러스터 위치는 벡터에 넣어준다.
	for (int i = 1; i <= R; i++) 
		for (int j = 1; j <= C; j++) 
			if (!visit[i][j] && map[i][j] != '.') 
				dfs(i, j, 1, v);

	if (v.empty()) return false;
	else {
		// 클러스터만 visit = true 만들어줌
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < v.size(); i++)
			visit[v[i].first][v[i].second] = 1;
		return true;
	}
}

 

벡터가 비어 있으면 붕 떠있는 클러스터가 없다는 뜻이다. 반면에 벡터에 원소가 있으면 붕 떠 있는 클러스터의 위치가 벡터에 저장되어 있다는 뜻이다. else 문에서 방문 배열을 주목하자. 방문 배열을 전부 0으로 다시 초기화하고, 클러스터의 위치만 방문 처리를 해줬다. 왜 그런지는 다음 함수에서 알 수 있다. 

 

 

우리는 이제 막대기를 던져서 미네랄을 캐고, 붕 떠 있는 클러스터를 벡터에 저장할 수 있게 되었다. 이제 붕 떠 있는 클러스터를 아래로 내려주기만 하면 된다. 나는 여기서 시간이 오래 걸렸다. 

 

 

먼저, 클러스터의 위치를 정렬할 필요가 있다. 클러스터를 아래로 내리기 위해서는 공백과 swap 해야하는데, swap은 클러스터의 가장 아래부터 시작해야 한다. 그렇지 않으면 꼬이게 된다. 따라서 클러스터 벡터를 행 기준 오름차순으로 정렬했다. 정렬 함수는 정답 코드를 참고하길 바란다. 

 

그 다음, 클러스터가 아래로 몇 칸 이동할지를 결정해야 한다. 클러스터의 모든 위치에서 바로 아래가 'x'가 아닌 것들 중, 다음 아래 'x'까지의 최소 거리를 찾으면 된다. 이게 무슨 뜻일까? 우선 클러스터가 붕 떠 있으면 무조건 한 칸은 이동할 수 있다. 따라서 바로 아래가 공백인 칸들만 고려하면 된다. 그래야 최소 한 칸은 움직일 수 있다는 뜻이니깐. 그런데 '다음 아래 x까지의 최소 거리'에서 다음 아래 x가 클러스터 내부의 위치면 안된다. 이를 구별하기 위해 visit 배열을 사용한다. 아까 visit 배열을 클러스터의 위치만 1로 초기화한게 이를 위해서다. 다음 아래 x 위치를 이미 방문했으면 패스해야한다. 말을 좀 어렵게 했는데 코드를 보면서 이해해보자. 

 

int get_len(vector<pair<int, int>>& v) {
    // 내려갈 거리를 반환해준다.
    // 바로 아래가 x가 아닌 것들 중에서 다음 아래 x까지의 최소거리

    int len = 1000000000; // 초기 최소값

    for (int i = 0; i < v.size(); i++) {
        pair<int, int> p = v[i];
        if (map[p.first + 1][p.second] == '.') {
            // 아래 칸이 공백이면 거리 잰다
            int tmp = 1;
            while (p.first + tmp <= R) {

                // 다음 아래 칸이 'x'면 더 못내려간다
                if (map[p.first + tmp][p.second] == 'x')
                    break;
                tmp++;
            }
            if (!visit[p.first + tmp][p.second]) {
                // 다음 'x'의 위치가 클러스터에 포함되지 않아야 한다
                len = min(len, tmp);
            }
        }
    }

    return len - 1;
}

 

 

정답 코드는 아래와 같다. 

 

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

char map[101][101];
int visit[101][101];
int sticks[100];
int move_row[4] = { 1,-1,0,0 };
int move_col[4] = { 0,0,1,-1 };
int R, C, n;

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

bool comp(const pair<int, int>& a, const pair<int, int>& b) {
	// first 기준 오름차순 정렬
	if (a.first == b.first) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}


void throw_stick(int row, int flag) {
	int r = R - row + 1; // 던지는 행

	if (flag == 0) {
		// flag = 0 이면 왼쪽에서 던짐
		for (int c = 1; c <= C; c++) {
			if (map[r][c] == 'x') {
				map[r][c] = '.';
				break;
			}
		}
	}
	else if (flag == 1) {
		// flag = 1 이면 오른쪽에서 던짐
		for (int c = C; c >= 1; c--) {
			if (map[r][c] == 'x') {
				map[r][c] = '.';
				break;
			}
		}
	}
}

void dfs(int x, int y, int flag, vector<pair<int, int>>& v) {
	// flag = 1 이면 벡터에 위치 넣어줌
	visit[x][y] = 1;
	if (flag == 1) v.push_back({ x, y });
	for (int i = 0; i < 4; i++) {
		int xx = x + move_row[i];
		int yy = y + move_col[i];
		if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) {
			if (!visit[xx][yy] && map[xx][yy] == 'x')
				dfs(xx, yy, flag, v);
		}
	}
}

bool air_cluster(vector<pair<int, int>>& v) {
	memset(visit, 0, sizeof(visit));

	// 1. 바닥 먼저 탐색
	for (int col = 1; col <= C; col++)
		dfs(R, col, 0, v);

	// 2. 이후 전체 탐색 - 클러스터 위치는 벡터에 넣어준다.
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			if (!visit[i][j] && map[i][j] != '.')
				dfs(i, j, 1, v);

	if (v.empty()) return false;
	else {
		// 클러스터만 visit = true 만들어줌
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < v.size(); i++)
			visit[v[i].first][v[i].second] = 1;
		return true;
	}
}

int get_len(vector<pair<int, int>>& v) {
	// 내려갈 거리를 반환해준다.
	// 바로 아래가 x가 아닌 것들 중에서 다음 아래 x까지의 최소거리

	int len = 1000000000; // 초기 최소값

	for (int i = 0; i < v.size(); i++) {
		pair<int, int> p = v[i];
		if (map[p.first + 1][p.second] == '.') {
			// 아래 칸이 공백이면 거리 잰다
			int tmp = 1;
			while (p.first + tmp <= R) {

				// 다음 아래 칸이 'x'면 더 못내려간다
				if (map[p.first + tmp][p.second] == 'x')
					break;
				tmp++;
			}
			if (!visit[p.first + tmp][p.second]) {
				// 다음 'x'의 위치가 클러스터에 포함되지 않아야 한다
				len = min(len, tmp);
			}
		}
	}

	return len - 1;
}

int main() {
	
	cin >> R >> C;

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

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> sticks[i];

	vector<pair<int, int>> v;

	for (int i = 0; i < n; i++) {
		// 1. 먼저 막대 던짐
		if (i % 2 == 0) throw_stick(sticks[i], 0);
		else throw_stick(sticks[i], 1);

		// 2. 떠있는 클러스터 있는지 확인
		while (air_cluster(v)) {
			// 스택에 있는거 끝까지 down 해줌
			// row 기준 오름차순 정렬
			sort(v.begin(), v.end(), comp);
			int len = get_len(v);
			int v_len = v.size();
			for (int k = 0; k < v_len; k++) {
				pair<int, int> p = v.back();
				v.pop_back();
				swap(map[p.first + len][p.second], map[p.first][p.second]);
			}
		}
	}
	
	print();
	
	return 0;
}