[백준] 17822번 원판 돌리기 _ 문제 풀이

from collections import deque
N, M, T = map(int, input().split())
circles = []
for _ in range(N):
    circles.append(list(map(int, input().split())))
for _ in range(T):
    x, d, k = map(int, input().split())
    for circle_idx in range(x-1, N, x):
        rotate_num = k if d == 0 else M-k
        # 배열 회전
        circles[circle_idx] = circles[circle_idx][-rotate_num:] + circles[circle_idx][:-rotate_num]       

    is_changed = False
    # 각 요소마다 0이 아니라면(0은 값이 같아서 지운 경우), BFS 를 수행한다.
    for c_idx in range(N):
        for m_idx in range(M):
            if circles[c_idx][m_idx] == 0:
                continue
            is_visited = [[False for __ in range(M)] for _ in range(N)]
            round_queue, same_queue = deque(), deque()
            round_queue.append((c_idx, m_idx))
            same_queue.append((c_idx, m_idx))
            # 같은 값들을 가진 얘들을 queue를 이용하여 전부 탐색
            while round_queue:
                c, m = round_queue.popleft()
                if is_visited[c][m]:
                    continue
                is_visited[c][m] = True

                # 후보 리스트들 만들기
                arr = [(c, m-1), (c, (m+1)%M)]
                if c == 0:
                    arr.append((c+1, m))
                elif c == N-1:
                    arr.append((c-1, m))
                else:
                    arr.extend([(c+1, m), (c-1, m)])

                # 후보 중 가능한 놈 빼서 확인
                for sub_c, sub_m in arr:
                    if circles[c][m] == circles[sub_c][sub_m] and is_visited[sub_c][sub_m] == False:
                        round_queue.append((sub_c, sub_m))
                        same_queue.append((sub_c, sub_m))

            if len(same_queue) == 1:
                continue
            while same_queue: # 값이 같은 얘들이 있으면 전부 0으로 만들어버림
                c, m = same_queue.popleft()
                circles[c][m] = 0
            is_changed = True

    # 한 번도 바꾸지 않았으면 
    if is_changed == False:
        cnt, total = 0, 0
        for c_idx in range(N):
            for m_idx in range(M):
                if circles[c_idx][m_idx]:
                    cnt += 1
                    total += circles[c_idx][m_idx]
        # 이 부분이 없으면 런타임 에러 (ZeroDivisionError) -> 한 번도 바꾸지 않고 모두 0인 경우가 있다고 보면 될 듯
        if cnt == 0:
            continue
        avg = total/cnt

        for c_idx in range(N):
            for m_idx in range(M):
                if circles[c_idx][m_idx]:
                    if circles[c_idx][m_idx] == avg:
                        continue
                    circles[c_idx][m_idx] = (circles[c_idx][m_idx]+1 if circles[c_idx][m_idx] < avg else circles[c_idx][m_idx]-1)

print(sum([sum(x) for x in circles]))