[백준][C++] 17822 원판 돌리기

17822번: 원판 돌리기

 

꺄~~ 

 

난생 처음으로 한 번에 맞힌 문제! 구현이 많은 문제였는데 너무 기쁘다~~ 구현을 이제 어느정도 할 수 있게 된 것 같지만, 최적화나 자료구조를 쓰는 부분은 아직도 구현에 비해서 훨씬... 부족한 것 같다. 사실 좋아할 게 아니라 반성해야지만...

 

그래도 정말정말정말 오랜만에 한 번에 맞힌 문제라 기분이 좋았다!!

 

 

알고리즘 설계

구조 

우선, 원판 전체를 Deque를 담는 배열로 저장해주었다. 2차원으로 만든 이유는 원판의 숫자 개수가 모두 같았고 인접한 수를 찾기 수월할 거라고 판단했기 때문이다.

 

vector나 배열이 아닌 Deque로 한 이유는 각 인덱스에 접근해야하고 시계방향, 반시계방향으로 돌릴 때 front, back의 삽입과 삭제가 자주 일어나기 때문이다.

 

 

또, 원판의 합과 숫자의 수는 매번 세지 않고 처음 입력받을 때 구해준다. 그리고 여러 과정을 거치며 숫자가 없어지거나 변할 때 구해진 합을 연산하고 수를 갱신했다. 매번 N*M번 연산하지 않아 효율적이라고 생각했다. 또, 이 합을 마지막에 출력만 할 수 있어 답을 구하기도 편했다.

 

지워져버린 수(x)는 -1로 통일했다. 

 

원판 돌리기

원판 돌리기는 앞서 말했듯 Deque의 특성을 이용하여 front, back에서 삽입과 삭제를 했다.

 

이미지로 이해하면 훨씬 쉽다. 숫자마다 다음 자리를 향해 이동해야하는 것처럼 보였지만, 사실은 front와 back을 삽입하고 지움으로써 배열이 한 칸씩 밀리게 되는 현상을 이용했다. 그렇게 되면 M번의 연산을 단 한 번으로 끝내는 것! 

 

K칸 이동이면 이 과정을 K번, X의 배수 원판에 해주었다.

 

 

인접한 수 지우기

인접한 수는 DFS 탐색으로 구했다. 

대부분의 DFS처럼 탐색할 좌표를 타고 타고 탐색하며 지울 리스트를 구성하고 지워주었다. visited 배열을 사용해서 방문을 체크해주었다.

 

이때, 원판의 특성을 주의해야한다. 일반적으로 인접한 좌표를 처리할 때 기준 NxM을 나간 좌표는 아예 검사를 해주지 않는 반면, 원판은 시작과 끝이 인접해있기 때문에 조금 다르게 처리해주어야 했다.

 

원형 큐를 구현할 때를 기억하면서 알고리즘을 구상했다. 

 

 

평균값 구해서 1씩 더하고 빼주기

지울 수가 없을 때, 평균을 구한 다음에 빼주는 작업을 했다. 위에서 말한 것처럼 이미 원판의 합, 숫자의 수를 가지고 있었기 때문에 평균값을 구해주었다.

 

여기에서도 주의할 점! 평균값은 정수 값이 아닌 실수 값으로 나와주어야 한다는 점.

 

2중 반복문을 사용해 각각의 수를 평균과 비교해주었다. 원판의 합 또한 갱신해주었다.

 

 

코드

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

deque<int> disk[51];
int radius, numCnt, tCnt, sum = 0, curAlive;

bool visited[51][51];
void DFS(int x, int y, vector<pair<int, int>>& vec);
bool Check();

int main()
{
	cin >> radius >> numCnt >> tCnt;
	curAlive = radius * numCnt;

	// 입력
	for (int i = 1; i <= radius; i++)
	{
		disk[i].resize(numCnt);

		for (int j = 0; j < numCnt; j++)
		{
			cin >> disk[i][j];
			sum += disk[i][j];
		}
	}

	while (tCnt--)
	{
		int target, direction, num;
		cin >> target >> direction >> num;
		num %= numCnt;

		// 돌리기
		for (int i = target; i <= radius; i += target)
		{
			for (int j = 0; j < num; j++)
			{
				if (!direction)	// 시계
				{
					disk[i].push_front(disk[i].back());
					disk[i].pop_back();
				}
				else
				{
					disk[i].push_back(disk[i].front());
					disk[i].pop_front();
				}
			}
		}

		// 체크 못하면 평균 구하기
		if (!Check() && curAlive > 0)
		{
			float aver = sum / (float)curAlive;

			for (int i = 1; i <= radius; i++)
			{
				for (int j = 0; j < numCnt; j++)
				{
					if (disk[i][j] < 0)continue;
					if (disk[i][j] == aver)continue;

					int val = (disk[i][j] > aver) ? -1 : 1;

					sum += val;
					disk[i][j] += val;
				}
			}
		}
	}

	cout << sum;
}

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };

void DFS(int x, int y, vector<pair<int, int>>& vec)
{
	visited[y][x] = true;

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

		if (ny > radius || ny <= 0) continue;
		nx = (nx + numCnt) % numCnt;

		if (disk[ny][nx] == disk[y][x] && !visited[ny][nx])
		{
			vec.push_back({ ny, nx });
			DFS(nx, ny, vec);
		}
	}
}

bool Check()
{
	bool check = false;

	fill(&visited[0][0], &visited[50][51], false);

	for (int i = 1; i <= radius; i++)
	{
		for (int j = 0; j < numCnt; j++)
		{
			if (visited[i][j] || disk[i][j] < 0) continue;

			vector<pair<int, int>> deleted;
			DFS(j, i, deleted);

			// 지울 수들이 있다면
			if (!deleted.empty())
			{
				check = true;
				deleted.push_back({ i, j });	// 현재 좌표도 넣기

				curAlive -= deleted.size();

				// 모두 지우고 sum 갱신
				for (pair<int, int> p : deleted)
				{
					sum -= disk[p.first][p.second];
					disk[p.first][p.second] = -1;
				}
			}
		}
	}

	return check;
}

 

재미있었던 문제~ 여러 단계를 해결하는 게 꼭 게임을 하는 것 같았다.