[백준] 원판 돌리기

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

17822번: 원판 돌리기

Deque를 활용한 구현, 시뮬레이션 문제입니다. 지문을 제멋대로 해석하는 바람에 살짝 해맸던 문제입니다. 회전한 다음 지워진 숫자가 없는 경우 평균을 구해 더하거나 빼는 작업을 진행해야하는데 각 원판별로 체크를 해서 진행하는 줄 알았는데 원판 전체에 대해 지워진 경우가 없을 때에만 작업을 해줘야합니다. 그리고 x배수의 원판을 회전시켜야하는데 이부분에서 실수가 있었습니다.

 

포인트가 되는 함수는 calculateCircle() 입니다. 인접해있는 같은 수를 찾는 과정에서 바로 지워버리면 더 지워져야하는데 지워지지 못하는 경우가 있습니다. 그렇기 때문에 isDeleted라는 2차원 boolean 배열에 삭제되어야하는 위치들을 저장하고 마지막에 반영하는 방식으로 풀이하면 이와 같은 문제를 해결할 수 있습니다.

 

 

# 문제링크: https://www.acmicpc.net/problem/17822
import sys
from collections import deque

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

# 삭제된 숫자의 위치를 표시
DELETE = -sys.maxsize

n, m, t = tuple(map(int, input().split()))

# 원판들
# 1 ~ N, 1이 가장 작은 원판, N이 가장 큰 원판
circles = [
    deque()
    for _ in range(n + 1)
]

# 원판들을 구성
for i in range(1, n + 1):
    nums = list(map(int, input().split()))
    for num in nums:
        circles[i].append(num)


def rotate(circle, d, cnt):
    # 시계 방향
    if d == 0:
        while cnt:
            circle.appendleft(circle.pop())
            cnt -= 1
    # 반시계 방향
    else:
        while cnt:
            circle.append(circle.popleft())
            cnt -= 1


def getAvg():
    sum = 0
    cnt = 0
    for i in range(1, n + 1):
        for j in range(m):
            if circles[i][j] != DELETE:
                sum += circles[i][j]
                cnt += 1

    return sum / cnt if cnt != 0 else sum

def calculateCircle():
    isDeleted = [
        [False] * m
        for _ in range(n + 1)
    ]

    # 양옆으로 같은 값이 있는지 확인
    for i in range(1, n + 1):
        for j in range(m):
            if circles[i][j] != DELETE and circles[i][j] == circles[i][(j + 1) % m]:
                isDeleted[i][j] = True
                isDeleted[i][(j + 1) % m] = True

    # 원판 위 아래로 같은 값이 있는지 확인
    for j in range(m):
        for i in range(1, n):
            if circles[i][j] != DELETE and circles[i][j] == circles[i + 1][j]:
                isDeleted[i][j] = True
                isDeleted[i + 1][j] = True

    isDeletedExist = False
    # isDeleted에 표시되어 있는 숫자들 지우기
    for i in range(1, n + 1):
        for j in range(m):
            if isDeleted[i][j]:
                isDeletedExist = True
                # 숫자를 지운다.
                circles[i][j] = DELETE

    # 지워진 숫자가 존재하면 종료
    if isDeletedExist:
        return

    #원판의 평균값 구하기
    avg = getAvg()

    # 현재 원판에서 지워진 수가 없는 경우
    for i in range(1, n + 1):
        for j in range(m):
            # 평균보다 큰 경우
            if circles[i][j] != DELETE and circles[i][j] > avg:
                circles[i][j] -= 1
            # 평균보다 작은 경우
            elif circles[i][j] != DELETE and circles[i][j] < avg:
                circles[i][j] += 1

for _ in range(t):
	# x: 돌릴 원판의 배수, d: 방향, k: 돌릴 횟수
    x, d, k = tuple(map(int, input().split()))

    mul = 2
    cur = x

    # x의 배수 원판들을 회전시킨다.
    while cur <= n:
        rotate(circles[cur], d, k)
        cur = x * mul
        mul += 1

    # 원판에 적힌 숫자들에 대한 처리
    calculateCircle()

ans = 0

#원판의 모든 합, 정답 구하기
for i in range(1, n + 1):
    ans += sum([
        x for x in circles[i] if x != DELETE
    ])

print(ans)