백준 17822 원판 돌리기 (파이썬)

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

17822번: 원판 돌리기

1. 원판 숫자의 총합을 nsum에 저장하고 개수를 nm에 저장한다

2. k를 m으로 나눈 나머지를 기준으로 원판 배열을 회전하고 방문 체크 배열 c도 같이 회전한다

3. 방문하지 않았던 숫자에 대해서 bfs를 수행한다

4. bfs로 이동하면서 y가 0보다 작으면 m-1, m-1보다 크면 0으로 바꿔서 원을 이루도록 한다

5. 다음 칸의 숫자가 같으면 체크하고 몇 개가 같은지 세는 xnct를 증가시킨다

6. return 값이 있으면 지운 숫자의 합만큼 nsum에서 빼주고 nm도 빼준다

   지운 숫자가 있음을 알려주는 flag를 1로 저장한다

7. 만약 모든 숫자를 지웠으면 0을 출력하고 끝낸다

   평균을 계산할 때 0으로 나누는 것을 방지할 수 있다

8. 지운 숫자가 없으면 문제의 조건대로 숫자를 바꾸고 nsum도 같이 빼거나 더해준다

9. 마지막에 nsum을 출력한다

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(x, y):
    q.append([x, y])
    xcnt = 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 0 <= nx < n and 0 <= ny < m and not c[nx][ny]:
                if a[x][y] == a[nx][ny]:
                    c[nx][ny] = 1
                    q.append([nx, ny])
                    xcnt += 1

    return xcnt

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

a, nsum, nm = [], 0, n*m
for _ in range(n):
    row = list(map(int, input().split()))
    a.append(row)
    nsum += sum(row)

q = deque()
c = [[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:
            a[i] = a[i][-k:] + a[i][:-k]
            c[i] = c[i][-k:] + c[i][:-k]
        else:
            a[i] = a[i][k:] + a[i][:k]
            c[i] = c[i][k:] + c[i][:k]

    flag = 0
    for i in range(n):
        for j in range(m):
            if not c[i][j]:
                cnt = bfs(i, j)
                if cnt:
                    nsum -= a[i][j] * cnt
                    nm -= cnt
                    flag = 1

    if nm == 0:
        print(0)
        sys.exit()

    if not flag:
        avg = nsum / nm
        for i in range(n):
            for j in range(m):
                if not c[i][j]:
                    if a[i][j] > avg:
                        a[i][j] -= 1
                        nsum -= 1
                    elif a[i][j] < avg:
                        a[i][j] += 1
                        nsum += 1
print(nsum)