boj, 백준) 17822. 원판 돌리기 (C / C++)

1. 문제 링크

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

17822번: 원판 돌리기

2. 문제 개요

원판을 여러 번 돌리고 나서 원판에 적힌 수의 합을 구하는 문제.

3. 문제 힌트!!

  주어진 입력값을 이해하기쉽게 배열에 저장하기.

  회전은 나머지 연산으로.

  인접한 숫자는 BFS로. 하지만 원통 형태이므로 만나는 부분은 경계 처리 잘하기.

  회전 - BFS 반복

4. 문제 풀이

우선 원판 정보를 입력받아야 한다.  직접 짠 코드는 행과 열을 바꾸어 주었다.(꼭 안 바꿔도 됨.)

 

문제의 예시처럼, 입력으로

[1 1 2 3]

[5 2 4 2]

[3 1 3 5]

[2 1 3 2]

가 들어온다고 가정하면 

행이 중심과의 거리가 될 것이고, 한 행에서 각 열은 원소가 될 것이다. ->(종이에 직접 그려가면서 하는 것 추천.)

이런 식으로 원판을 배열에 담고, 각 원판마다 회전을 한다.

 

회전을 할 때 원판의 내부 원소가 0~3번까지 있고 지금 x번의 원소가 시계방향으로 k만큼 움직인다고 하면, (x + k) % 4가 된다.

즉, 크기가 size가 n이고 지금 x번, 시계방향으로 k만큼 움직이면 (x + k)% n이 되는 것이다. 

반시계 방향으로 회전하는 것은 시계방향으로 (n - k)번 움직인 것이므로 (x + (n - k) % n이 된다. (n - k이 음수가 될 수 있지만, 문제의 조건에서는 회전량이 원판 하나의 원소의 개수보다 크지 않다고 했으므로 괜찮음)

 

이렇게 회전을 하고 나서, 인접한 것 중에 같은 번호를 가진 게 있는지 찾아야 한다.

BFS로 Grouping 하듯이 구현하면 된다.  (뒤에 나오겠지만 값이 0 인부분은 이전 Turn에서 '지운'부분이므로 0인 부분은 Grouping에 참여하면 안 된다.)

단, 이 문제의 핵심인 것이 경계 처리를 할 때, 원판이 맞닿는 부분은 조건문을 통해서 위치를 잘 조정시켜주어야 한다는 것이다.

풀이의 시작에 적었던 행렬을 기준으로 한다면 원판 구현 시 0번째 열과 3번째 열이 맞닿게 된다.

그래서 다음 x좌표가 -1이 되거나 4가 될 때, 적절히 조건문을 사용하여 -1 -> 3으로, 4 -> 0으로 바꿔주어야 한다. 그러고 나서 경계를 벗어났는지 검사해야 한다.

 

위의 조건을 고려하여 Gruoping 된 원소들은 모두 0으로 값을 바꿔주고(지우는 것), 그렇지 않은 원소들은 평균을 계산하기 위해 더하고 개수도 세어둔다.

 

만약에 1개라도 지운 것, 즉, Grouping 된 것이 없다면 위의 평균 정보를 사용하여 평균보다 큰 것은 -1, 작은 것은 +1을 해준다.

 

이과정을 T번 반복하고 나서 원판의 모든 원소의 값을 출력한다.

 

5. 코드

#include <cstdio>
#include <queue>
using namespace std;

int map[51][51];
int n, m, t;

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

void cpmap(int dest[51][51], int src[51][51])
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dest[i][j] = src[i][j];
	return;
}
int main(void)
{
	scanf("%d %d %d", &n, &m, &t);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &map[i][j]);

	while (t--)
	{
		int x, d, k;
		scanf("%d %d %d", &x, &d, &k);
		int clone[51][51] = { 0 };
		cpmap(clone, map);

		for (int i = 1; i <= n; i++)
		{
			if (i%x == 0)
			{
				if (d == 0)
				{
					for (int j = 1; j <= m; j++)
						clone[i][(j - 1 + k) % m + 1] = map[i][j];
				}
				else
				{
					for (int j = 1; j <= m; j++)
						clone[i][(j - 1 + (m - k)) % m + 1] = map[i][j];
					
				}
			}
			else
			{
				for (int j = 1; j <= m; j++)
					clone[i][j] = map[i][j];
			}
		}

		//remove
		bool visited[51][51] = { false, };
		
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (!visited[i][j] && clone[i][j] != 0)
				{
					int num = 1;
					queue<pair<int, int>>q;
					visited[i][j] = true;
					q.push(make_pair(i, j));

					while (!q.empty())
					{
						int cx = q.front().second;
						int cy = q.front().first;
						q.pop();

						for (int dir = 0; dir < 4; dir++)
						{
							int nx = cx + dx[dir];
							int ny = cy + dy[dir];

							//x is circular
							if (nx == m + 1) nx = 1;
							if (nx == 0) nx = m;

							if (nx <1 || ny <1 || nx >m || ny >n || visited[ny][nx])
								continue;
							if (clone[cy][cx] != clone[ny][nx])
								continue;

							visited[ny][nx] = true;
							q.push(make_pair(ny, nx));
							num++;
						}
					}
					if (num == 1)
					{
						visited[i][j] = false;
					}
				}
			}

		double avg=0;
		int sum=0, div=0;
		bool flag = false;
		for(int i=1;i<=n;i++)
			for (int j = 1; j <= m; j++)
			{
				if (visited[i][j])
				{
					clone[i][j] = 0;
					flag = true;
				}
				sum += clone[i][j];
				if (clone[i][j] != 0)
					div++;
			}

		if (!flag)
		{
			avg = (double)sum / (double)div;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= m; j++)
				{
					if (clone[i][j] != 0)
					{
						if (clone[i][j] < avg)
							clone[i][j]++;
						else if (clone[i][j] > avg)
							clone[i][j]--;
					}
				}
		}
		cpmap(map, clone);
	}
	int ret = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			ret += map[i][j];
	printf("%d", ret);
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~