[백준 17822번] 원판 돌리기

mokomoko·2022년 2월 22일

1. 문제

반지름이 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번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

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

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

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

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

제한 사항

시간 : 1 초
메모리 : 512 MB
2 ≤ N, M ≤ 50
1 ≤ T ≤ 50
1 ≤ 원판에 적힌 수 ≤ 1,000
2 ≤ xi ≤ N
0 ≤ di ≤ 1
1 ≤ ki < M

입력

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

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

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

출력

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

- 키워드

Deque를 이용하면 쉽게 풀 수 있다.

인접한 수가 같지 않을 때 평균값과 같으면 계산하면 안 된다.

2. 풀이

문제를 봤을 때 딱 deque가 떠올랐다.

구현자체에는 크게 시간이 걸리지 않았지만, ~~역시 문제 제대로 안 읽어서~~

평균값과 같을 경우 +1 or -1을 한다는 조건이 없었다. 그래서 5번째 테스트케이스에서

왜 틀렸는지 찾느라 시간이 조금 걸렸다.

문제가 장황하게 적혀있지만, 그림을 보면 쉽게 이해할 수 있다.

N * M 사이즈의 원판에서

"x의 배수" 번째 원판을 "d 방향" 으로(0은 시계 1은 반시계) "k 칸"만큼 돌리는 걸 T번 한단 뜻이다.

5번째 테스트케이스를 보면,

4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2

이런 원판이 주어진다는 것인데 사실 2차원 배열이랑 크게 다를바가 없다.

첫 번째 회전은 2의 배수번째 원판을 반시계 방향으로 4칸 이동하는 것이다.

그림과 같이 Deque에서 가장 앞 부분을 뒤로 보내는 것을 4번 하면 된다.

인접한 수 중 같은 수는 없으므로 평균 값보다 작거나 큰 값은 +-1을 하도록 한다.

평균 값이 5이므로 5를 제외한 나머지 값은 +-1을 한다.

두 번째 회전은 3의 배수번째 원판을 시계 방향으로 1칸 이동하는 것이다.

이번엔 Deque 끝 부분을 앞으로 보내는 것을 1번 하면 된다.

인접한 수 중 같은 수일 경우를 찾는다.

이 때 주의할 점은 인접한 수가 짝수인 경우가 아닐 경우가 있으므로,

같은 수의 인접한 수들의 위치를 저장하고 나중에 한번에 0으로 바꿔준다.

상하좌우로 탐색하되 행은 벗어나지 않게 열의 끝부분은 반대 쪽을 탐색해야한다.

세 번째 회전은 2의 배수번째 원판을 반시계 방향으로 2칸 이동하는 것이다.

Deque 앞 부분에서 끝으로 2번 보낸다.

인접한 수 중 같은 값을 찾는다.

인접한 수가 존재하므로 0으로 바꾸고 여기서 회전을 멈추고 deque에 저장된 값을 전부 더한다.

정답은 26이다.

문제를 제대로 이해하는 것이 가장 중요한 거 같다.

3. 소스코드

import sys
from collections import deque
input = sys.stdin.readline


def move(q,d,k):
	if d == 0:
		for _ in range(k):
			q.appendleft(q.pop())
	else:
		for _ in range(k):
			q.append(q.popleft())

def check(board,N,M):
	dx,dy = [-1,0,1,0],[0,1,0,-1]
	del_point = []
	num_point = []
	cnt = 0
	total = 0
	for row in range(N):
		for col in range(M):
			if board[row][col] > 0:
				cnt += 1
				total += board[row][col]
				num_point.append([row,col])
				for drow,dcol in zip(dx,dy):
					if 0 <= row+drow < N and -1 <= col+dcol < M:
						if board[row][col] == board[row+drow][col+dcol] != 0:
							del_point.append([row,col])
							break
					elif 0 <= row+drow < N and col+dcol == M:
						if board[row][col] == board[row+drow][0] != 0:
							del_point.append([row,col])
							break
	if del_point:
		for i in del_point:
			row,col = i
			board[row][col] = 0
	else:
		for i in num_point:
			row,col = i
			if board[row][col] > total/cnt:
				board[row][col] -= 1
			elif board[row][col] < total/cnt:
				board[row][col] += 1

def solution(N,M,T,board,spin):
	answer = 0
	for i in spin:
		x,d,k = i
		for j in range(x-1,len(board),x):
			move(board[j],d,k)
		check(board,N,M)

	for row in board:
		answer += sum(row)

	return answer

if __name__ == "__main__":
	N,M,T = map(int,input().split())
	board = []
	for _ in range(N):
		board.append(deque(list(map(int,input().split()))))
	spin = []
	for _ in range(T):
		spin.append(list(map(int,input().split())))
	print(solution(N,M,T,board,spin))