[알고리즘] 원판 돌리기

포인트

• 생각보다 까다롭지만 문제 자체는 이해하는 것이 그렇게는 어렵지 않으면서도 구현은 어려운? 무슨 말이지?

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(row: int, col: int) -> int:
	"""
	같은 숫자, 방문하지 않는 곳, y는 범위 넘어가면 넘겨주기
	:param row:
	:param col:
	:return:
	"""
	q = deque()
	q.append([row, col])
	count = 0
	while q:
		x, y = q.popleft()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			
			if ny < 0:
				ny = m - 1
			elif ny > m - 1:
				ny = 0
			
			if not (0 <= nx < n and 0 <= ny < m):
				continue
			
			if visited[nx][ny] == 0 and data[x][y] == data[nx][ny]:
				visited[nx][ny] = 1
				q.append([nx, ny])
				count += 1
	
	return count


n, m, t = map(int, input().split())
data, total_numbers, numbers = [], 0, n * m

for _ in range(n):
	row = list(map(int, input().split()))
	data.append(row)
	total_numbers += sum(row)

visited = [[0] * m for _ in range(n)]

for _ in range(t):
	x, d, k = map(int, input().split())
	k %= m
	# 어차피 크기가 커도 변환을 할 수 있다. 
	for i in range(x - 1, n, x):
		# 배수 만큼 변환:
		if d == 0:
			# 이렇게 리스트를 회전할 수 있다.
			data[i] = data[i][-k:] + data[i][:-k]
			visited[i] = visited[i][-k:] + visited[i][:-k]
		else:
			data[i] = data[i][k:] + data[i][:k]
			visited[i] = visited[i][k:] + visited[i][:k]
	
	flag = 0
	for i in range(n):
		for j in range(m):
			if not visited[i][j]:
				cnt = bfs(i, j)
				# 개수를 찾는다
				if cnt:
					total_numbers -= data[i][j] * cnt
					# 개수 반영한다.
					numbers -= cnt
					flag = 1
	
	if numbers == 0:
		total_numbers = 0
		break
	elif flag == 0:
		avg = total_numbers / numbers
		for i in range(n):
			for j in range(m):
				if not visited[i][j]:
					if data[i][j] > avg:
						data[i][j] -= 1
						total_numbers -= 1
					elif data[i][j] < avg:
						data[i][j] += 1
						total_numbers += 1

print(total_numbers)