[python] 백준 17822 원판 돌리기

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

17822번: 원판 돌리기

 

문제 해결

• 원판을 돌리는 코드를 짤 수 있어야한다.(시계방향과 반시계방향 2가지 나눠서)
• X가 되어 사라진 것은 0으로 표시한다.(없애는 것은 BFS를 통해 한번에 없앤다.)
• 변화가 없을 때는 평균을 구해서 0이상의 수중 평균보다 작은 것은 +1 큰 것은 -1을 계산해준다.

 

CODE

from collections import deque


def bfs(x, y):
    global flag
    visited[x][y] = 1
    que = deque()
    que.append((x, y))
    dxs = [-1, 1, 0, 0]
    dys = [0, 0, -1, 1]
    memo = [(x, y)]
    while que:
        p, q = que.popleft()
        for dx, dy in zip(dxs, dys):
            np = p + dx
            nq = (q + dy) % m
            if 0 <= np < n and visited[np][nq] == -1 and board[p][q] == board[np][nq]:
                que.append((np, nq))
                visited[np][nq] = 1
                memo.append((np, nq))
    if len(memo) > 1:
        for a, b in memo:
            board[a][b] = 0
            flag = True


def simulate(num):
    global board, flag
    x, d, k = order[num][0], order[num][1], order[num][2]
    for j in range(len(board)):
        if (j + 1) % x == 0:
            if d == 0:
                board[j] = board[j][m - k : m] + board[j][: m - k]
            elif d == 1:
                board[j] = board[j][k:] + board[j][:k]
    avg = 0
    mem = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                continue
            else:
                bfs(i, j)
    if not flag:
        for i in range(n):
            for j in range(m):
                if board[i][j] > 0:
                    avg += board[i][j]
                    mem += 1
        if mem!=0:
            avg /= mem
            for i in range(n):
                for j in range(m):
                    if board[i][j] == 0:
                        continue
                    elif board[i][j] > avg:
                        board[i][j] -= 1
                    elif board[i][j] < avg:
                        board[i][j] += 1


if __name__ == "__main__":
    n, m, t = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    order = []
    for _ in range(t):
        x, d, k = map(int, input().split())
        order.append([x, d, k])
    for i in range(t):
        visited = [[-1 for _ in range(m)] for _ in range(n)]
        flag = False
        simulate(i)
    answer = 0
    for i in range(n):
        for j in range(m):
            answer += board[i][j]
    print(answer)