파이썬 | 백준 | 17822 | 원판 돌리기

solution

1. bfs 이용해 같은 수가 인접해있으면 0으로 바꿈

 

20%대에서 틀림 반례 찾아봐야 함

# 17822, 원판 돌리기
import sys
from collections import deque

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


def bfs(x, y, n):
    global flag
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    near = False
    while q:
        a, b = q.popleft()
        if a != 0:
            nx = a-1
            if circle[nx][b] == n and visited[nx][b] == 0:
                near = True
                visited[nx][b] = visited[a][b]+1
                q.append((nx, b))

        if a != N-1:
            nx = a + 1
            if circle[nx][b] == n and visited[nx][b] == 0:
                near = True
                visited[nx][b] = visited[a][b]+1
                q.append((nx, b))

        if b - 1 != y:
            if b == 0:
                ny = M -1
            else:
                ny = b -1
            if circle[a][ny] == n and visited[a][ny] == 0:
                near = True
                visited[a][ny] = visited[a][b] + 1
                q.append((a, ny))

        if b + 1 != y:
            if b == M-1:
                ny = 0
            else:
                ny = b+1
            if circle[a][ny] == n and visited[a][ny] == 0:
                near = True
                visited[a][ny] = visited[a][b] + 1
                q.append((a, ny))

        if near:
            flag = True
            circle[a][b] = 0


def bfs_all():
    global flag

    for i in range(N):
        for j in range(M):
            if visited[i][j] == 0 and circle[i][j] != 0:
                bfs(i, j, circle[i][j])

def rotate_clockwise(arr, n):
    q = deque(arr)
    for i in range(n):
        q.appendleft(q.pop())
    return list(q)


def rotate_anticlockwise(arr, n):
    q = deque(arr)
    for i in range(n):
        q.append(q.popleft())
    return list(q)


def updateAvg(avg):
    s = 0
    for i in range(N):
        for j in range(M):
            if circle[i][j] > avg:
                circle[i][j] -= 1
            elif circle[i][j] < avg and circle[i][j] != 0:
                circle[i][j] += 1
            s += circle[i][j]
    return s


def calcSum():
    s = 0
    for i in range(N):
        for j in range(M):
            s += circle[i][j]
    return s


N, M, T = map(int, sys.stdin.readline().split())
circle = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

flag = True
res = 0
for _ in range(T):
    x, d, k = map(int, sys.stdin.readline().split())
    for i in range(x-1, N, x):
        if d == 0:
            circle[i] = rotate_clockwise(circle[i], k)
        else:
            circle[i] = rotate_anticlockwise(circle[i], k)
    flag = False  # 인접한 수 있는지
    visited = [[0] * M for _ in range(N)]
    bfs_all()

    if not flag:
        cnt, sum = 0, 0
        for i in range(N):
            for j in range(M):
                if circle[i][j] != 0:
                    cnt += 1
                    sum += circle[i][j]
        avg = sum/cnt
        res = updateAvg(avg)
if flag:
    print(calcSum())
else:
    print(res)

 

 

sum은 예약어→변수명 또는 함수명으로 사용할 수 없다.

 

문제 출처 www.acmicpc.net/problem/17822

17822번: 원판 돌리기