17822번 - 원판 돌리기

문제

17822번: 원판 돌리기 (acmicpc.net)

17822번: 원판 돌리기

풀이

간단한 구현 문제지만, 각 행이 큐로 되어있어 인접 노드를 탐색할 때 주의해야한다. 어이없게도 "배수"를 반복문을 통해 2배씩 곱해주는 것으로 계산해서 많은 시간을 날렸다. 또한 평균을 구할 때 cnt 가 0이 되는 때도 있음을 주의해야한다.

from collections import deque

N,M,T = map(int,input().split())
# 0:W 1:R 2:B
circles = [deque()]
for i in range(N):
    circles.append(deque(map(int, input().split())))

# 동 서 북 남
dRow = [0,0,-1,1]
dCol = [1,M-1,0,0]

for _ in range(T):
    # 배수, 방향, 칸 수
    x,d,k = map(int,input().split())
    k *= 1 if d == 0 else -1
    # 회전
    temp = x
    while x <= N:
        circles[x].rotate(k)
        x += temp
    # 인접하면서 같은 수가 있는지 탐색
    new_circles = [deque([*elem]) for elem in circles]
    sum_value = 0
    cnt = 0
    flag = False
    for i in range(1,N+1):
        for j in range(M):
            if circles[i][j] > 0:
                sum_value += circles[i][j]
                cnt += 1
            if new_circles[i][j] > 0:
                q = deque()
                q.append((i,j))
                while q:
                    r,c = q.popleft()
                    for dir in range(4):
                        nr, nc = r + dRow[dir], (c + dCol[dir]) % M
                        if 1 <= nr <= N and circles[nr][nc] == circles[i][j] and new_circles[nr][nc] > 0:
                            new_circles[nr][nc] = 0
                            flag = True
                            q.append((nr, nc))
    circles = new_circles
    if cnt == 0:
        print(0)
        break
    avg = sum_value / cnt
    if not flag:
        for i in range(1,N+1):
            for j in range(M):
                if circles[i][j] > 0:
                    if circles[i][j] > avg:
                        circles[i][j] -= 1
                    elif circles[i][j] < avg:
                        circles[i][j] += 1
else:
    answer = sum(map(sum,circles))
    print(answer)