백준 18500 - 미네랄 2

 

 

문제 설명

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

---

 

 

 

 

 

 

제한 사항

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

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

---

 

 

 

 

 

 

풀이

문제를 요약하면, 왼쪽, 오른쪽 번갈아가며 특정 높이에 있는 미네랄을 없앤다.

미네랄이 없어지면 다른 미네랄과 연결되지 않고 공중에 떠 있는 미네랄이 존재한다.

그런 미네랄은 모양을 유지하며 밑으로 떨어진다.

미네랄은 바닥에 닿거나 다른 미네랄에 닿으면 멈춘다.

 

정리하자면 다음과 같은 과정을 거친다.

1. 입력받은 높이에 왼쪽 혹은 오른쪽의 미네랄을 제거한다.
2. 공중에 떠 있는 미네랄 뭉치가 있는지 확인한다.
   • 공중에 떠 있는 미네랄 뭉치가 있다면 최대한 밑으로 내린다.

 

미네랄을 제거하는 것은 왼쪽 혹은 오른쪽에서 순회를 하면 되기 때문에 간단하다.

공중에 떠 있는 미네랄 뭉치를 확인하는 과정은 BFS를 통해 확인할 수 있다.

이 과정에서는 없어진 미네랄로부터 네방향에 있는 미네랄에서 시작하면 된다.

빨간 칸이 없어진다면 해당 칸에서 네방향에 미네랄만 클러스터(뭉치)가 바뀌기 때문이다.

네 방향에 대해 BFS를 진행해 뭉치를 분리하는 과정에서 제일 밑에 칸(땅)에 닿았는지 확인한 뒤, 땅에 닿았다면 움직일 필요가 없다.

반대로 땅에 닿지 못했다면 밑으로 미네랄 뭉치를 떨어뜨려야 한다.

void CheckInAir(vector<vector<char>>& Mineral, int i, int j)
{
	for (int k = 0; k < 4; k++)
	{
		vector<vector<bool>> visited(Mineral.size(), vector<bool>(Mineral[0].size(), false));
		queue<pair<int, int>> q;

		int startY = i + dy[k];
		int startX = j + dx[k];

		if (startY < 0 || startY >= Mineral.size() || startX < 0 || startX >= Mineral[0].size()) continue;
		if (Mineral[startY][startX] == '.') continue;
		q.push({ startY, startX });
		visited[startY][startX] = true;

		bool bTouchGround = false;
		while (!q.empty())
		{
			auto [y, x] = q.front();
			q.pop();

			if (y == Mineral.size()-1)
			{
				bTouchGround = true;
				break;
			}

			for (int i = 0; i < 4; i++)
			{
				int newY = y + dy[i];
				int newX = x + dx[i];

				if (newY < 0 || newY >= Mineral.size() || newX < 0 || newX >= Mineral[0].size()) continue;
				if (visited[newY][newX] || Mineral[newY][newX] == '.') continue;

				visited[newY][newX] = true;
				q.push({ newY,newX });
			}
		}

		if (bTouchGround) continue;
		else MoveDown(Mineral, visited);
	}
}

 

미네랄 뭉치를 떨어뜨리는 과정은 고정된(땅에 닿은)부분과 공중에 떠 있는 부분의 차이가 가장 작은 만큼 이동하면 된다.

예제 2번을 진행하다 보면 위와 같은 상황이 된다.

빨간 부분이 없어지면 왼쪽에 있는 미네랄 뭉치가 공중에 뜨게 된다.

그럼 해당 미네랄 뭉치가 땅과 떨어져 있는 최소 높이를 구해 떨어뜨리면 된다.

연두색 부분이 땅과 떨어진 부분이며 이때는 최소 높이가 2로 동일하다.

따라서 윗 부분(공중에 떠 있는 미네랄)을 2씩 떨어뜨리면 된다.

void MoveDown(vector<vector<char>>& Mineral, vector<vector<bool>>& visited)
{
	int minDiff = Mineral.size() - 1;

	for (int j = 0; j < Mineral[0].size(); j++)
	{
		int ground = Mineral.size();

		for (int i = Mineral.size()-1; i >= 0; i--)
		{
			if (Mineral[i][j] == 'x' && !visited[i][j]) ground = i;
			if (Mineral[i][j] == 'x' && visited[i][j])
			{
				minDiff = min(minDiff, ground - i - 1);
			}
		}
	}

	for (int i = Mineral.size() - 1; i >= 0; i--)
	{
		for (int j = 0; j < Mineral[0].size(); j++)
		{
			if (visited[i][j])
			{
				Mineral[i + minDiff][j] = 'x';
				Mineral[i][j] = '.';
			}
		}
	}
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>

using namespace std;

vector<int> dy = { 0, -1, 0, 1 };
vector<int> dx = { 1, 0, -1, 0 };

enum
{
	LEFT,
	RIGHT
};

void MoveDown(vector<vector<char>>& Mineral, vector<vector<bool>>& visited)
{
	int minDiff = Mineral.size() - 1;

	for (int j = 0; j < Mineral[0].size(); j++)
	{
		int ground = Mineral.size();

		for (int i = Mineral.size()-1; i >= 0; i--)
		{
			if (Mineral[i][j] == 'x' && !visited[i][j]) ground = i;
			if (Mineral[i][j] == 'x' && visited[i][j])
			{
				minDiff = min(minDiff, ground - i - 1);
			}
		}
	}

	for (int i = Mineral.size() - 1; i >= 0; i--)
	{
		for (int j = 0; j < Mineral[0].size(); j++)
		{
			if (visited[i][j])
			{
				Mineral[i + minDiff][j] = 'x';
				Mineral[i][j] = '.';
			}
		}
	}
}

void CheckInAir(vector<vector<char>>& Mineral, int i, int j)
{
	for (int k = 0; k < 4; k++)
	{
		vector<vector<bool>> visited(Mineral.size(), vector<bool>(Mineral[0].size(), false));
		queue<pair<int, int>> q;

		int startY = i + dy[k];
		int startX = j + dx[k];

		if (startY < 0 || startY >= Mineral.size() || startX < 0 || startX >= Mineral[0].size()) continue;
		if (Mineral[startY][startX] == '.') continue;
		q.push({ startY, startX });
		visited[startY][startX] = true;

		bool bTouchGround = false;
		while (!q.empty())
		{
			auto [y, x] = q.front();
			q.pop();

			if (y == Mineral.size()-1)
			{
				bTouchGround = true;
				break;
			}

			for (int i = 0; i < 4; i++)
			{
				int newY = y + dy[i];
				int newX = x + dx[i];

				if (newY < 0 || newY >= Mineral.size() || newX < 0 || newX >= Mineral[0].size()) continue;
				if (visited[newY][newX] || Mineral[newY][newX] == '.') continue;

				visited[newY][newX] = true;
				q.push({ newY,newX });
			}
		}

		if (bTouchGround) continue;
		else MoveDown(Mineral, visited);
	}
}

void Throw(vector<vector<char>>& Mineral, int height, int dir)
{
	int x = -1;

	if (dir == LEFT)
	{
		for (int j = 0; j < Mineral[height].size(); j++)
		{
			if (Mineral[height][j] == 'x')
			{
				x = j;
				break;
			}
		}
	}
	else
	{
		for (int j = Mineral[height].size()-1; j >= 0; j--)
		{
			if (Mineral[height][j] == 'x')
			{
				x = j;
				break;
			}
		}
	}

	if (x != -1)
	{
		Mineral[height][x] = '.';
		CheckInAir(Mineral, height, x);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int R, C, N;
	cin >> R >> C;

	vector<vector<char>> Mineral(R, vector<char>(C));

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> Mineral[i][j];
		}
	}

	cin >> N;
	vector<int> Stick(N);

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		Stick[i] = R - temp;
	}

	for (int i = 0; i < N; i++)
	{
		Throw(Mineral, Stick[i], i % 2);
	}

	for (int i = 0; i < Mineral.size(); i++)
	{
		for (int j = 0; j < Mineral[0].size(); j++)
		{
			cout << Mineral[i][j];
		}
		cout << "\n";
	}

	return 0;
}

---