백준 17822번 원판 돌리기

문제 링크입니다: https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기

여타 다른 삼성 코딩 테스트처럼 문제를 잘 읽고 그대로 구현하면 되는 문제였습니다.

원판을 시계방향 혹은 반시계방향으로 돌리기 때문에 저는 원판을 간단하게 구현하기 위해 덱 (deque)으로 구현했습니다. (해당 내용은 turnRullet 함수를 참고해주세요)

주의할 점은 덱으로 구현했기 때문에 인접한 요소를 찾을 때 덱의 front()와 덱의 back()이 인접했다고 표시하는 부분은 별도로 처리해줘야 합니다.

또한, 평균을 정수가 아닌 실수로 구하여 비교해야 한다는 점을 주의해야 합니다.

 

	#include <iostream>
	#include <queue>
	#include <vector>
	#include <deque>
	using namespace std;
	const int MAX = 50 + 1;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { { 1, 0 },{ -1, 0 },{ 0, 1 },{ 0, -1 } };
	int N, M, T;
	int X, D, K;
	deque<int> dq[MAX];
	void turnRullet(void)
	{
	for (int x = X; x <= N; x += X)
	{
	for (int k = 0; k < K; k++)
	{
	if (D == 0)
	{
	int temp = dq[x].back();
	dq[x].pop_back();
	dq[x].push_front(temp);
	}
	else
	{
	int temp = dq[x].front();
	dq[x].pop_front();
	dq[x].push_back(temp);
	}
	}
	}
	}
	bool eraseNumbers(void)
	{
	bool erasedNumbers = false;
	// 인접한 수 처리
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (dq[i][j] == 0)
	{
	continue;
	}
	queue<pair<int, int>> q;
	int value = dq[i][j];
	q.push({ i, j });
	bool visited[MAX][MAX] = { false, };
	visited[i][j] = true;
	vector<pair<int, int>> v;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	v.push_back({ y, x });
	for (int d = 0; d < 4; d++)
	{
	int nextY = y + moveDir[d].y;
	int nextX = x + moveDir[d].x;
	// 위 아래는 인접 X
	if (nextY == 0 || nextY > N)
	{
	continue;
	}
	// 양 옆 인접 O
	if (nextX == -1)
	{
	nextX = M - 1;
	}
	else if (nextX == M)
	{
	nextX = 0;
	}
	if (visited[nextY][nextX])
	{
	continue;
	}
	if (dq[nextY][nextX] == value)
	{
	visited[nextY][nextX] = true;
	q.push({ nextY, nextX });
	}
	}
	}
	// 인접한 숫자가 있을 경우에만 제거
	if (v.size() >= 2)
	{
	erasedNumbers = true;
	for (int k = 0; k < v.size(); k++)
	{
	int y = v[k].first;
	int x = v[k].second;
	dq[y][x] = 0;
	}
	}
	}
	}
	return erasedNumbers;
	}
	void changeNumbers(void)
	{
	int sum = 0;
	int cnt = 0;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (dq[i][j] == 0)
	{
	continue;
	}
	sum += dq[i][j];
	cnt++;
	}
	}
	double average = (double)sum / cnt;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	if (dq[i][j] == 0)
	{
	continue;
	}
	if (dq[i][j] > average)
	{
	dq[i][j]--;
	}
	else if (dq[i][j] < average)
	{
	dq[i][j]++;
	}
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	int num;
	cin >> num;
	dq[i].push_back(num);
	}
	}
	for (int t = 0; t < T; t++)
	{
	cin >> X >> D >> K;
	turnRullet();
	bool flag = eraseNumbers();
	if (flag)
	{
	continue;
	}
	changeNumbers();
	}
	int result = 0;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	result += dq[i][j];
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~