[C/C++] 백준 - 17822번 : 원판 돌리기

BOJ/시물레이션

[C/C++] 백준 - 17822번 : 원판 돌리기

JWonK 2021. 8. 4. 15:03

728x90

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

17822번: 원판 돌리기

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀

www.acmicpc.net

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.


1번 원판을 시계 방향으로 1칸 회전	2, 3번 원판을 반시계 방향으로 3칸 회전	1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

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

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

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

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

< 구해야하는 것 >

입력한 원판을 조건에 따라 다른 행동을 취한 후 마지막에 남은 원판에 적힌 수의 합

< 사용해야하는 자료구조 및 알고리즘 >

일단 이 문제에서 원판은 각각 독립적으로 이루어져있다. 그리고 그 원판을 시계방향 또는 반시계방향으로 돌려야한다.

여기에 가장 적합한 자료구조는 나는 덱(Deque)이라고 판단했다. 회전시키는 방향에 따라 앞 또는 뒤에서 원소를 하나 빼서 반대방향으로 삽입하는 과정으로 회전시키는 걸 표현할 수 있다고 생각했고, 이 과정을 가장 쉽게 행할 수 있는 자료구조를 덱이라고 생각했다.

인접한 원소를 확인하는 법은 옆 원소를 확인하는 방법, 다른 원판이지만 같은 위치에 놓여있는 원소를 확인하는 방법을 달리 생각해 함수를 총 6개 만들었다.

6개 만든 이유는 :

1. 다른 원판이지만 같은 위치의 인접한 원소를 확인

(1). 가장 안쪽에 있는 원판은 더 이상 안쪽에 원판이 존재하지 않기 때문에 바로 바깥 원판 같은 위치만 확인하면 된다.

(2). 가장 바깥쪽에 있는 원판은 더 이상 바깥쪽에 원판이 존재하지 않기 때문에 바로 안쪽 원판 같은 위치만 확인하면 된다

(3). 위 2가지 제외를 경우하고는 해당 원판 바깥 원판과 안쪽 원판이 모두 존재하기 때문에 2가지 원판을 모두 확인해주는 함수를 작성해준다

2. 같은 원판에서의 원소 확인

(1). 덱이라는 자료구조를 사용했기 때문에 덱에서의 인덱스가 0인 원소의 양옆을 확인하는 경우에는 왼쪽 원소가 그 덱의 가장 뒤에 있는 원소가 된다. (원형리스트라 생각하면 된다, 양끝 원소가 이어져 원을 이루는 모양)

(2). 해당 덱에서 가장 마지막 원소를 확인하는 경우, 왼쪽 원소가 그 덱에서 첫번째 원소가 된다.

(3). 위 2가지 경우를 제외하고는 양쪽 모두 원소가 존재하기 때문에, 양 옆을 검사해주는 함수

-->> 이렇게 해서 각각의 경우의 수를 나눠주어 6개의 함수를 만들어 인접한 수 중 같은 수가 존재하는지 확인해주었다.

그리고 bool변수를 통해 하나라도 인접한 수 중 같은 수가 존재하는지 확인해주었다. 만약 bool변수의 변화가 없다면, 인접한 수 중 같은 수가 존재하지 않는다는 것이므로 예외 경우인 평균을 구해 값을 변화시켜주는 함수 행하게 만들어주었다.

-> 이 문제에서 평균값을 구할 때는 실수형으로 구해주어야한다 -> double Avg = (double)Sum / (double)Cnt

그리고 이런 식으로 값의 변화가 연속적으로 이루어지는 문제 유형은 한 번 행해지고 나서 그 형태를 저장해주는 과정이 필요하다. 그 이유는, 저장해주는 과정이 없으면 원래는 검사를 확인해야하는 값이지만, 그 전 과정에서 이 값이 없어져버릴수도 있기 때문이다. 그래서 Copy함수를 통해 원래의 모양은 저장해주고, 값의 변화가 일어나는 덱은 따로 최신화시켜주었다.

위 과정을 T번 반복하면 된다!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
using namespace std;

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

deque<int> dq[52], dq2[52];
int N, M, T;
bool isChange = false;

void Input_Data() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			int x; cin >> x;
			dq[i].push_back(x);
		}
	}
}

void Adj_Up(int data, int pos1, int pos2) {
	if (dq[pos1+1][pos2] != -1 && dq[pos1 + 1][pos2] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1 + 1][pos2] = -1;
	}
}

void Adj_Down(int data, int pos1, int pos2) {
	if (dq[pos1-1][pos2] != -1 && dq[pos1 - 1][pos2] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1 - 1][pos2] = -1;
	}
}

void Adj_Check_Up_Down(int data, int pos1, int pos2) {
	if (dq[pos1+1][pos2] != -1 && dq[pos1 + 1][pos2] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1 + 1][pos2] = -1;
	}
	if (dq[pos1-1][pos2] != -1 && dq[pos1 - 1][pos2] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1 - 1][pos2] = -1;
	}
}

void Adj_left(int data, int pos1, int pos2) {
	if (dq[pos1][dq[pos1].size()-1] != -1 && dq[pos1][dq[pos1].size()-1] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][dq[pos1].size()-1] = -1;
	}
	if (dq[pos1][pos2+1] != -1 && dq[pos1][pos2 + 1] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][pos2 + 1] = -1;
	}
}

void Adj_Right(int data, int pos1, int pos2) {
	if (dq[pos1][0] != -1 && dq[pos1][0] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][0] = -1;
	}
	if (dq[pos1][pos2-1] != -1 && dq[pos1][pos2 - 1] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][pos2 - 1] = -1;
	}
}

void Adj_Check_Left_Right(int data, int pos1, int pos2) {
	if (dq[pos1][pos2+1] != -1 && dq[pos1][pos2 + 1] == data) {
		isChange = true;
		if (dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][pos2 + 1] = -1;
	}
	if (dq[pos1][pos2-1] != -1 && dq[pos1][pos2 - 1] == data) {
		isChange = true;
		if(dq[pos1][pos2] != -1) dq[pos1][pos2] = -1;
		dq[pos1][pos2 - 1] = -1;
	}
}

void Change_Value_Round() {
	int total = 0, Cnt = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (dq[i][j] == -1) continue;
			total += dq[i][j]; Cnt++;
		}
	}

	double Average = (double)total / (double)Cnt;

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (dq[i][j] == -1) continue;
			if (dq[i][j] > Average) dq[i][j] -= 1;
			else if (dq[i][j] < Average) dq[i][j] += 1;
		}
	}
}

int Answer() {
	int Answer = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (dq[i][j] == -1) continue;
			Answer = Answer + dq[i][j];
		}
	}
	return Answer;
}

void Copy() {
	for (int i = 1; i <= N; i++) {
		if (!dq2[i].empty()) dq2[i].clear();
		for (int j = 0; j < M; j++) {
			int x = dq[i][j];
			dq2[i].push_back(x);
		}
	}
}

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

	Input_Data();
	while (T--) {
		int Number, Dir, go;
		cin >> Number >> Dir >> go;

		int ps = 1;
		while (1) {
			if (Number * ps > N) break;
			int n = Number * ps;
			for (int Go = 0; Go < go; Go++) {
				if (!Dir) {
					int ChangeData = dq[n].back();
					dq[n].pop_back();
					dq[n].push_front(ChangeData);
				}
				else {
					int ChangeData = dq[n].front();
					dq[n].pop_front();
					dq[n].push_back(ChangeData);
				}
			}
			ps++;
		}

		Copy();

		isChange = false;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				int x = dq2[i][j];
				if (x == -1) continue;
				// 따로 해줘야하는세로
				if (i == 1 or i == N) {
                	// 안쪽에 원판이 존재하지 않을 때, 바깥 원판만 확인
					if (i == 1) Adj_Up(x, i, j);
                    // 바깥 원판이 존재하지 않을 때, 안쪽 원판만 확인
					else Adj_Down(x, i, j);
				}
				else Adj_Check_Up_Down(x, i, j);
				
				//따로 해줘야하는 가로
				if (j == 0 or j == M - 1) {
                	// 덱의 첫번째 원소 확인, 마지막 원소를 확인해주어야 함
					if (j == 0) Adj_left(x, i, j);
                    // 덱의 마지막 원소 확인, 첫번째 원소를 확인해주어야 함
					else Adj_Right(x, i, j);
				}
				else Adj_Check_Left_Right(x, i, j);
			}
		}
		
        // 인접한 수 중 같은 값을 가지는 원소가 존재하지 않는 경우
		if (!isChange) 
			Change_Value_Round();
	}

	cout << Answer() << '\n';

	return 0;
}

728x90

'BOJ > 시물레이션' 카테고리의 다른 글

[C/C++] 백준 - 16637번 : 괄호 추가하기 (삼성 A형 기출문제) (0)	2021.08.06
[C/C++] 백준 - 19237번 : 어른 상어 (0)	2021.08.05
[C/C++] 백준 - 16986번 : 인싸들의 가위바위보 (0)	2021.08.02
[C/C++] 백준 - 10836번 : 여왕벌 (0)	2021.07.30
[C/C++] 백준 - 17406번 : 배열 돌리기4 (0)	2021.07.29

현재글[C/C++] 백준 - 17822번 : 원판 돌리기

원

250x250

백준, Spring, 구현, 동적 계획법, 투포인터, 스프링, 트리, 알고리즘, 완전탐색, 자료구조, 너비우선탐색, 동적계획법, 다이나믹 프로그래밍, 시물레이션, 다익스트라, 정렬, 문자열, 깊이 우선 탐색, 수학, 백트래킹,

Today :
Yesterday :

원