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

삼성 SW 역량 테스트

https://www.acmicpc.net/workbook/view/1152

ㄴ원판 돌리기

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

 

 

 

l 문제

 

1. 중심이 같은 원판들을 주어진 조건에 따라 회전시킨다.

2. 원판 원판은 반지름이 1부터 N까지 크기 순서대로 놓여있다. ( 1이 가장 위 )

3. 원판의 숫자 각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. ( x, y )는 ( x + 1, y ), ( x - 1, y ), ( x, y -1 ) ,( x, y + 1) 과 인접하다. 간단하게 동서남북 4방향으로 생각하면 된다. 주의할 점 y = 0 일 때 y - 1 위치는 -1이 아닌 M-1로 y = M-1일 때 y + 1 위치는 M이 아닌 0으로 해주어야 한다.

4. 회전 시키는 원판만 돌아가며, 정확하게 간격 만큼 돌아간다. i번째 회전할때 사용하는 변수는 xi, di, ki이다. 번호가 xi의 배수인 원판을 di 방향으로 ki칸 회전시킨다. ( di = 0 : 시계 방향, di = 1 : 반시계 방향 )

 

 

l 입력

 

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다. 다음 T개의 줄에 xi, di, ki가 주어진다.

 

 

l 출력

 

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

 

 

l 풀이

 

조건에 따라 시뮬레이션 하면 된다.

오른쪽, 아래, 왼쪽, 위 ( {0,1}, {1,0}, {0,-1}, {-1,0} ) 인접 검사 함수 {    if       0번째 수 && 왼쪽 방향 : x = i, y = M-1    else if M-1번째 수 && 오른쪽 방향 : x =i, y = 0    else    방향에 따라    범위 검사 } 시뮬레이션 함수 {   1. 회전   2. 인접한 수 찾아내기   3. 인접한 수를 제거   4. 인접한 수가 없는 경우 처리 }

인접한 수 찾기, 제거

모두 반복하면서 인접한 수를 찾으면 check 해 두고 check된 것들을 일괄적으로 제거하면 된다. 제거는 마음대로 구현하면 되는데 나는 제거된 수를 -1로 간주하여 -1로 변경해주었다.

문제에 실수할 수 있는 부분

1. 모든 원판의 수가 제거된 경우 sum / 0 으로 인해 런타임 에러가 발생할 수 있다. 따라서 모든 원판의 수가 제거된 경우를 꼭 검사해주어야 한다. 2. 평균 평균이 정수가 아니라 실수라고 생각하고 풀어야 한다. avg = 22 / 6 = 3.6666 avg > 3 이므로 3은 4가 된다. avg < 4 이므로 4는 3이 된다. 그렇다면 avg = 120 / 24 = 5.000 일 때 avg와 5를 비교한다면? 같은 경우에 대해서는 문제에 제시되어 있지 않으므로 별다른 처리를 하지 않는다.

 

 

l  코드

 

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

int N, M, T, x, d, k, ans, deleted_cnt;
vector<vector<int>> board;
bool adj[51][50];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1 ,0 ,-1, 0 };

bool is_adjacent(const int &i, const int &j, const int &r)
{
	int tx, ty;
	if (j == 0 && r == 2) tx = i, ty = M - 1;
	else if (j == M - 1 && r == 0) tx = i, ty = 0;
	else tx = i + dx[r], ty = j + dy[r];
	if (tx >= 1 && ty >= 0 && tx <= N && ty < M)
	{
		if (board[tx][ty] == -1) return false;
		if (board[i][j] == board[tx][ty])
		{
			adj[i][j] = true, adj[tx][ty] = true;
			return true;
		}
	}
	return false;
}
void simulation()
{
	register int i, j, r, c;
	double sum = 0.0;
	bool adjacent;

	// 1. 회전
	c = k % M;
	for (i = x; i <= N; i += x)
	{
		if (d) rotate(board[i].begin(), board[i].begin() + c, board[i].end());
		else rotate(board[i].rbegin(), board[i].rbegin() + c, board[i].rend());
	}

	// 2. 인접한 수 찾아내기
	adjacent = false;
	for (i = 1; i <= N; ++i)
	{
		for (j = 0; j < M; ++j)
		{
			if (board[i][j] == -1) continue;
			sum += board[i][j];

			for (r = 0; r < 4; ++r)
				if (is_adjacent(i, j, r))
					adjacent = true;
		}
	}
	// 3. 인접한 수를 제거
	if (adjacent)
	{
		for (i = 1; i <= N; ++i)
		{
			for (j = 0; j < M; ++j)
			{
				if (adj[i][j])
				{
					board[i][j] = -1;
					++deleted_cnt;
				}
				adj[i][j] = false;
			}
		}
		return;
	}

	if (deleted_cnt == M * N) return;
	// 4. 인접한 수가 없는 경우 처리
	sum /= (double)(N * M - deleted_cnt);
	for (i = 1; i <= N; ++i)
	{
		for (j = 0; j < M; ++j)
		{
			if (board[i][j] == -1) continue;
			if ((double)board[i][j] > sum) --board[i][j];
			else if((double)board[i][j] < sum) ++board[i][j];
		}
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> T;

	board.resize(N + 1, vector<int>(M));
	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 0; j < M; ++j)
			cin >> board[i][j];

	for (i = 0; i < T; ++i)
	{
		cin >> x >> d >> k;
		simulation();
		if (deleted_cnt == M * N) break;
	}
	for (i = 1; i <= N; ++i)
		for (j = 0; j < M; ++j)
			if (board[i][j] != -1)
				ans += board[i][j];

	cout << ans;
	return 0;
}