[백준][삼성 SW 역량 테스트][Gold 3][C++] 17822 원판 돌리기

문제

백준 삼성 SW 역량 테스트 기출 문제 - 17822 원판 돌리기 (Gold 3)

17822번: 원판 돌리기

 

---

문제 풀이

접근 방식

원판을 T번 회전시킨 후, 원판에 적힌 수의 합을 구하는 문제이다.

 

우선, 원판의 값을 입력받은 후, for문을 통해 T번 회전을 수행하였다.

d가 0일 때는 시계 방향으로 회전시키고, d가 1일 때는 반시계 방향으로 회전시켜야 한다.

그래서 d가 0일 때는 -1로 값을 바꿔주었고,

아래의 for문을 통해 x의 배수의 원판들을 d 방향으로 k번 회전시켜주었다.

for (int b = 1; b * x <= N; b++) {
	int temp[51];
	for (int c = 0; c < M; c++) {
		temp[(c + M - k * d) % M] = board[b * x][c];
	}
	memcpy(board[b * x], temp, sizeof(temp));
}

 

회전시킨 후에는 원판의 각 숫자들을 탐색하며 인접한 숫자가 같은 경우 제거해주었다.

숫자를 제거하기 위해 아래와 같이 remove 함수를 만들어주었다.

bool remove(int x, int y, int v) {
	bool check = false;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0], ny = (y + dir[i][1] + M) % M;
		if (nx == 0 || nx > N) continue;
		if (board[nx][ny] == v && !visit[nx][ny]) {
			visit[nx][ny] = 1;
			check = true;
			board[nx][ny] = 0;
			remove(nx, ny, v);
		}
	}
	return check;
}

 

매개변수 v와 탐색할 위치의 숫자가 일치하는 경우에는 그 값을 제거해주었고,

remove 함수를 재귀적으로 호출하여 그 위치에서의 인접한 숫자들을 다시 탐색해주도록 구현해주었다.

 

1번 원판은 마지막 원판과 인접하지 않고, 마지막 원판 역시 1번 원판과 인접하지 않다.

그래서 nx의 값이 0이거나 N보다 큰 경우에는 탐색을 수행하지 않았다.

반면, 같은 원판 내에서는 양옆의 숫자가 모두 인접한 숫자이기 때문에 양쪽을 모두 탐색할 수 있도록 구현하였다.

 

또한, 인접한 숫자 중 같은 숫자가 존재해야만 처음 탐색을 시작한 곳의 숫자를 제거할 수 있기 때문에

인접한 숫자가 v와 같은 경우에는 true를 리턴해주어서 처음 탐색한 곳의 숫자를 제거해주었다.

 

제거된 숫자가 아예 없는 경우에는 평균을 구하여

평균보다 작은 숫자에는 1을 더해주었고, 큰 숫자에는 1을 빼주었다.

이때 총합계인 total의 값도 1을 더하거나 빼주어야 모든 테스트 케이스를 통과할 수 있다.

(평균을 쉽게 구하기 위해 인접한 숫자들을 탐색할 때 남아있는 수의 개수와 합계를 구해주었다.)

 

위의 과정을 T번 수행하여 최종적으로 남은 수의 합을 출력해주었다.

---

풀이 코드 - C++

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

int N, M, T;
int board[51][51];
bool visit[51][51];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

bool remove(int x, int y, int v) {
	bool check = false;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir[i][0], ny = (y + dir[i][1] + M) % M;
		if (nx == 0 || nx > N) continue;
		if (board[nx][ny] == v && !visit[nx][ny]) {
			visit[nx][ny] = 1;
			check = true;
			board[nx][ny] = 0;
			remove(nx, ny, v);
		}
	}
	return check;
}

int main() {
	cin >> N >> M >> T;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
		}
	}

	int x, d, k, total, cnt;
	for (int a = 0; a < T; a++) {
		// 원판 회전
		cin >> x >> d >> k;
		if (d == 0) d = -1;
		for (int b = 1; b * x <= N; b++) {
			int temp[51];
			for (int c = 0; c < M; c++) {
				temp[(c + M - k * d) % M] = board[b * x][c];
			}
			memcpy(board[b * x], temp, sizeof(temp));
		}

		// 인접 숫자 제거
		bool check = true;
		total = 0, cnt = 0;
		memset(visit, 0, sizeof(visit));
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 0) continue;
				visit[i][j] = 1;
				if (remove(i, j, board[i][j])) {
					board[i][j] = 0;
					check = false;
				}
				else {
					cnt++;
					total += board[i][j];
				}
			}
		}

		// 없는 경우
		if (check) {
			float avg = (float) total / cnt;
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j < M; j++) {
					if (board[i][j] == 0) continue;
					if (board[i][j] > avg) {
						board[i][j]--;
						total--;
					}
					else if (board[i][j] < avg) {
						board[i][j]++;
						total++;
					}
				}
			}
		}
	}

	cout << total;
}

실행 결과

실행 결과 : 통과 (4ms)