[Python] 백준 17822번: 원판 돌리기

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

17822번: 원판 돌리기

 

---

 

# 정리

인접한 곳에 같은 숫자가 존재하는지, 존재할경우 이를 제거하는 일을 간단한 dfs를 이용해서 풀었는데

문제는, 최대 재귀 깊이를 늘려주지 않으면 80%쯤 가서 런타임 에러가 발생한다.

sys.setrecursionlimit을 이용하면 해결 가능하다.

아마도 순위권 코드의 속도와 내 코드의 속도가 차이가 나는 이유는 dfs문 때문이겠ㅈ;;;

 

2차원 배열의 요소(=element)들을 collections 모듈의 deque객체로 정의해주면,

deque객체의 rotate함수로 시계방향 또는 반시계방향으로 회전하는 것을 쉽게 해결할 수 있다.

 

오늘은 너무 피곤해서..

시간 효율성 높이는 작업까지는 무리..!

 

---

 

# Code

from collections import deque
import sys
sys.setrecursionlimit(10000)
 
def dfs(x, y):
    global num
    for dx, dy in zip(dxs, dys):
        nx, ny = x+dx, (y+dy)%m
        if nx<0 or nx>=n: continue
        if board[nx][ny] == value:
            num += 1
            board[nx][ny] = 0
            dfs(nx, ny)
 
 
if __name__ == '__main__':
    n, m, t = map(int, input().split())
    board = [deque(list(map(int, input().split()))) for _ in range(n)]
 
    dxs = (0, 0, -1, 1)
    dys = (-1, 1, 0, 0)
 
    t_num = n*m
    t_sum = 0
    for i in range(n):
        t_sum += sum(board[i])
 
    for _ in range(t):
        c, d, k = map(int, input().split())
        for i in range(c, n+1, c):
            if d == 0: board[i-1].rotate(k) # 시계방향
            else: board[i-1].rotate(-k)     # 반시계방향
 
        P = 0
        for x in range(n):
            for y in range(m):
                if board[x][y] == 0: continue
                num = 0
                value = board[x][y]
                dfs(x, y)
                if num != 0: # 인접, 동일한 수가 존재함
                    P = 1
                    t_num -= num
                    t_sum -= num*value
        if t_num == 0: print(0); break
        if P == 0: # 인접, 동일한 수가 존재하지 않음.
            avg = t_sum / t_num
            for i in range(n):
                for j in range(m):
                    if board[i][j] == 0: continue
                    if board[i][j] < avg:
                        board[i][j] += 1
                        t_sum += 1
                    elif board[i][j] > avg:
                        board[i][j] -= 1
                        t_sum -= 1
    if t_num != 0: print(t_sum)