백준 17822번: 원판 돌리기 (C++)

문제 링크 : www.acmicpc.net/problem/17822

 

시뮬레이션, 구현 문제라서 딱히 특별한 알고리즘은 없다.

 

<전체적인 알고리즘>

1. 원판의 층과 원판마다의 수를 이차원배열로 저장하면 편하다. (x축 - 원판 층, y축- 원판의 숫자들)

2. x의 배수들의 원판들을 조건만큼 회전 시켜준다. (ex - 배열의 앞의 숫자를 떼어서 맨 뒤에 붙이면 반시계방향 )

3. 원판들의 수를 탐색하면서 인접한 같은 수들을 제거해준다 (dfs를 이용)

4. 인접한 같은 수가 하나도 없다면 평균 값을 구해서 조건에 따라 증가 또는 감소를 시켜준다.

5. 2,3,4를 끝날 때 까지 수행

 

<주의할 점>

1.원판인것을 잊으면 안된다. 탐색할 때 배열의 끝을 넘어가면 배열의 시작점으로, 배열의 시작점을 벗어나면 배열의 끝으로 이동하여야 한다.

2. 원판에 더이상 숫자가 없다면 (전체적인 알고리즘 설명의)4번을 수행해서는 안된다. 평균 값을 구할 때 0으로 나눠버려서 에러가 발생한다.

<전체 코드>

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

deque<int> plate[52];
int n, m, t;
bool check[52][52];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

bool dfs(int id, int index,int origin_num)  //인접한 것들 탐색하며 같은 수 전부 지워 나가기
{
	bool has_same = false;
	for (int d = 0; d < 4; d++)
	{
		int next_id = id + dir[d][0];   //다음 원판 id
		int next_index = (index + dir[d][1])%m;   //다음 수의 index(한 층 안에서 인접 index)
		if (next_index == -1)next_index=m-1;
		if (next_id<1 || next_id>n)continue;
		if (plate[next_id][next_index] == 0)continue;
		if (check[next_id][next_index])continue;

		if(plate[next_id][next_index]==origin_num) 
		{
			check[next_id][next_index] = true;
			plate[next_id][next_index] = 0;
			dfs(next_id, next_index, origin_num);
			has_same = true;
		}
	}
	return has_same;
}

void move_plate(int x, int d, int k)  //원판 회전
{
	if (d == 0)  //시계 방향으로 회전
	{
		for (int id = x; id <= n; id=id+x)  //x의 배수원판 전부 회전
		{
			for (int i = 0; i < k; i++)
			{
				int tmp = plate[id][m - 1];
				plate[id].pop_back();
				plate[id].push_front(tmp);
			}
		}
	}
	else  //반시계 방향으로 회전
	{
		for (int id = x; id <= n; id = id + x)  //x의 배수 원판 전부 회전
		{
			for (int i = 0; i < k; i++)
			{
				int tmp = plate[id][0];
				plate[id].pop_front();
				plate[id].push_back(tmp);
			}
		}
	}
	
	fill(&check[0][0], &check[50][51], 0);
	bool istrue = false;	
	for (int i = 1; i <= n; i++)      //원판 인접하고 같은 수들 전부 제거
	{
		for (int j = 0; j < m; j++)
		{
			if (check[i][j])continue;   //방문한 적 있으면 스킵 
			if (plate[i][j] == 0)continue;
			if (dfs(i, j, plate[i][j]))  
			{
				istrue = true;
			}
		}		
	}

	if (!istrue)  // 지울게 없었다면
	{
		int sum = 0;
		int count = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (plate[i][j] == 0)continue;
				sum += plate[i][j];
				count++;				
			}
		}
		if (count == 0)return;
		double avg = ((double)sum) / count;  //평균값 구하기
		
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (plate[i][j] == 0)continue;
				if (plate[i][j] > avg)plate[i][j]--;  //평균값 보다 크면 --
				else if (plate[i][j] < avg)plate[i][j]++;  //작으면 ++
			}
		}
	}
}

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

	cin >> n >> m >> t;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int num;
			cin >> num;
			plate[i].push_back(num);
		}
	}
	
	for (int i = 0; i < t; i++)
	{
		int x, d, k;
		cin >> x >> d >> k;
		move_plate(x, d, k); 
	}
	
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			sum += plate[i][j];
		}
	}

	cout << sum;

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.