[파이썬 | BOJ | 17822] 원판 돌리기

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

17822번: 원판 돌리기

문제

반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

아래 그림은 N = 3, M = 4인 경우이다.

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

다음 그림은 원판을 회전시킨 예시이다.

1번 원판을 시계 방향으로 1칸 회전

2, 3번 원판을 반시계 방향으로 3칸 회전

1, 3번 원판을 시계 방향으로 2칸 회전

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

1. 번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
2. 원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
   1. 그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
   2. 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.

입력

첫째 줄에 N, M, T이 주어진다.

둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.

다음 T개의 줄에 xi, di, ki가 주어진다.

출력

원판을 T번 회전시킨 후 원판에 적힌 수의 합을 출력한다.

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ xi ≤ N
• 0 ≤ di ≤ 1
• 1 ≤ ki < M

추가 예시

 

초기 상황

x1 = 2, d1 = 0, k1 = 1 2번, 4번 원판을 시계 방향으로 1칸 돌린 후

인접하면서 수가 같은 것을 모두 지운 후

x2 = 3, d2 = 1, k2 = 3 3번 원판을 반시계 방향으로 3칸 돌린 후

인접하면서 수가 같은 것을 모두 지운 후

 

x3 = 2, d3 = 0, k3 = 2 2, 4번 원판을 시계 방향으로 2칸 돌린 후

인접하면서 수가 같은 것이 없다. 따라서, 평균 22/6 보다 작은 수는 +1, 큰 수는 -1 했다.

x4 = 3, d4 = 1, k4 = 1 3번 원판을 반시계 방향으로 1칸 돌린 후

인접하면서 수가 같은 것을 모두 지운 후

 

풀이

주어진 명령에 맞게 원판을 회전하고, 인접한것들을 지우고, 지울게 없으면 평균에 대한 대소를 비교해서 값을 변경하는 등의 주어진 동작을 모두 구현해야 한다.

 

일단 원판을 회전하기 때문에, deque을 사용해서 left, right에서 pop과 append를 사용할 수 있도록 한다. (리스트에서 pop(0)는 시간복잡도가 O(n)이다.)

또한 상 하 좌 우로 인접하는 값들을 탐색해야 하는데, 좌, 우의 경우에는 원형이므로 범위를 넘어가면 알맞게 처리해야하며, 상, 하의 경우에는 좌, 우와는 달리 서로 원형의 범위가 아니므로 범위를 넘어가는 것에 있어서 처리를 할 필요가 없다.

하지만 구현의 간편함을 위해서 그냥 맨 윗줄 및 맨 아랫줄에 임의의 데이터를 넣어서 처리하면 따로 범위 처리를 해 줄 필요가 없다.

 

회전하는 것은 방향에 맞춰서 pop과 append를 사용해서 간단하게 구현할 수 있다.

인접하는 것들을 지우는 것에서 유의해야 할 점은, 만약 어떤 값을 탐색하는 중에 해당 값에 인접하는 모든 값들을 지워버리게 되면, 지우는 동작으로 인해서 원래 3개가 연속으로 인접하고 있었다면, 2개만 지워지게 된다.

([2, 2, 2]의 형태에서 0번째 2를 탐색해서 0번째와 1번째를 지우게 된다면 [0, 0, 2]가 되어 2번째 2가 결국 사라지지 않게 된다.)

따라서 지워질 데이터라는 것을 표현하기 위해서 지워질 데이터를 음수로 표현하고, 한번에 지우는 것으로 구현한다.

 

평균에 대한 대소를 비교할 때도, 주의할 점은 cnt = 0인 경우에 div0 에러가 날 수 있다는 것이고, 평균값과 같은 경우에는 더하지도, 빼지도 않는다.

 

모든 기능을 구현한 코드는 다음과 같다.

 

 

# [파이썬 | BOJ | 17822] 원판 돌리기
 
import sys
from collections import deque
read = sys.stdin.readline
 
# 상 하 좌 우
drdc = [[-1, 0], [1, 0], [0, -1], [0, 1]]
 
N, M, T = map(int, read().split())
circle = [deque([0 for _ in range(M)])]
for _ in range(N):
    circle.append(deque(map(int, read().split())))
circle.append(deque([0 for _ in range(M)]))
x = []
d = []
k = []
 
for _ in range(T):
    # d가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
    X, D, K = map(int, read().split())
    x.append(X)
    d.append(D)
    k.append(K)
 
#print(circle)
for index in range(T):
    X, D, K = x[index], d[index], k[index]
    tx = X
 
    while tx <= N:
        for _ in range(K):
            if D == 0:
                circle[tx].appendleft(circle[tx].pop())
            else:
                circle[tx].append(circle[tx].popleft())
        tx += X
    flag = True
    sumVal = 0
    cntVal = 0
    for r in range(1, N+1):
        for c in range(M):
            if circle[r][c] <= 0:
                continue
            sumVal += circle[r][c]
            cntVal += 1
 
            for i in range(4):
                nr, nc = r + drdc[i][0], c + drdc[i][1]                
                if nc == -1:
                    nc = M-1
                elif nc == M:
                    nc = 0
 
                if circle[r][c] == abs(circle[nr][nc]):
                    circle[r][c] *= -1
                    if circle[nr][nc] > 0:
                        circle[nr][nc] *= -1
                    flag = False
    for r in range(1, N+1):
        for c in range(M):
            if circle[r][c] < 0:
                circle[r][c] = 0
    #print(circle)
 
    if flag and cntVal > 0:
        avgVal = sumVal/cntVal
        #print(avgVal)
        for r in range(1, N+1):
            for c in range(M):
                if circle[r][c] == 0:
                    continue
                if circle[r][c] > avgVal:
                    circle[r][c] -= 1
                elif circle[r][c] < avgVal:
                    circle[r][c] += 1
    #print(circle)
 
ans = 0
for r in range(1, N+1):
    for c in range(M): 
        ans += circle[r][c]
print(ans)