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

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

공부 날짜 : 2022.09.27
정답 참조 여부 : X

원판을 돌리면서 인접한 칸과 값이 같으면 지우고 지워진 칸이 없다면 평균값과 비교해서 작은수는 +1 큰 수는 -1 하며 값을 지워나가고 최종적으로 원판에 남은 값의 합을 구하는 문제이다.

---

원판을 돌리는 과정을 리스트로 표현해야하는데 보통 큐자료구조를 활용하여 표현한다.
큐 구조를 사용하기 위해서 collections모듈의 deque를 사용하는게 일반적이지만 insert와 pop를 이용해서 큐 구조처럼 표현 했으며 둘의 차이는 아직까지 이해하지 못했다. 큐 구조가 좀더 메모리나 시간적으로 효율적이라는데 아직까지 insert와 pop로 구현했다고 시간초과나 메모리초과가 일어난적은 없었다.

시계 방향으로 돌리는건 자료의 맨마지막에 있는 값을 (index = [-1]) 맨 앞에 넣는 방식( insert(0,value) )으로 표현했고

cycle[spin_pan].insert(0, cycle[spin_pan].pop(-1))

반시계 방향으로 돌리는건 맨 앞에 있는 값을 (index = [0]) 맨뒤로 넣는방식( append )으로 구현했다.

cycle[spin_pan].append(cycle[spin_pan].pop(0))

---

최근 가장 헷갈리는건 동시작업or순차작업이냐의 과정이 많이 헷갈린다.
이번 문제에서 모든 값에대해서 인접한 값이 있으면 없애는 동시작업이다.
초기 작성시 해당 사항을 신경쓰면서 코드를 작성했으나 결과적으로 순차적으로 앞에 인접한 값이 있으면 수정되어 후에 체크하는 값이 수정된 후의 값과 비교해서 에러가 많이 발생했다.

해결 방식은 기존에 비교해야하는 값은 보존하고 새 변수를 만들어서 새 변수에 값을 담아간후에 새변수로 갱신해주는 방식으로 하고있다. 해당부분을 신경써서 버그픽스하는 시간을 줄일 수 있도록 하자.

소스코드

import sys
from copy import deepcopy
input = sys.stdin.readline

n,m,k = map(int, input().split())

cycle = []
#원판 정보 받아오기
for _ in range(n):
    cycle.append(list(map(int, input().split())))
    
#리스트에서 index+1까지 같은지 탐색하기 위한 추가적인 리스트
#(n+1)개의 리스트가 존재하며 n번 index까지 존재함
#(n-1)인덱스에서 index+1번 과 비교하기위한 추가
cycle.append([0 for _ in range(m)])   
    
order = []
#회전 명령 받아오기
#0은 시계방향 1은 반시계방향
for _ in range(k):
    order.append(list(map(int,input().split())))
    
    
    
    
    
#원판을 회전시키는 함수
def turn(spin_pan, dir, turn_count):
    #시계방향
    if dir == 0:
        for _ in range(turn_count):
            cycle[spin_pan].insert(0, cycle[spin_pan].pop(-1))
    #반시계방향
    elif dir == 1:
        for _ in range(turn_count):
            cycle[spin_pan].append(cycle[spin_pan].pop(0))

        
        
        
        
#order의 과정을 모두 수행
while order:
    spin_num, dir, turn_count = order.pop(0)
    
    #spin_num에서부터 n까지 spin_num을 더하며(spin_num의 배수) 회전
    for spin_pan in range(spin_num-1, n, spin_num):
        turn(spin_pan, dir, turn_count)
    
    new_cycle = [[0 for _ in range(m)] for _ in range(n+1)]
    #원판 전체에서 같은것이 있는지 체크하는 변수
    check_same = False
    #모든 칸에 대해서
    for i in range(n):
        for j in range(m):
            #삭제된 칸이라면 패스
            if cycle[i][j] == 0:
                continue
                
            #해당 칸이 인접한 칸과 같은지 체크하는 변수
            check_same_this = False
            if cycle[i][j] == cycle[i-1][j]:
                check_same = True
                check_same_this = True
            
            if cycle[i][j] == cycle[i+1][j]:
                check_same = True
                check_same_this = True
                
            if cycle[i][j] == cycle[i][(j+1)%m]:
                check_same = True
                check_same_this = True
                
            if cycle[i][j] == cycle[i][j-1]:
                check_same = True
                check_same_this = True
            
            #같은 것이 없다면 값을 그대로 가져감
            #있으면 new_cycle가 이미 0이므로 따로 변경없음
            if check_same_this == False:
                new_cycle[i][j] = cycle[i][j]
          
    #전체 원판에 대해서 같은것이 없다면    
    if check_same == False:
        sum_ = 0
        count_ = 0
        
        for i in range(n):
            for j in range(m):
                if cycle[i][j] != 0:
                    sum_ += cycle[i][j]
                    count_ += 1
                    
        for i in range(n):
            for j in range(m):
                if cycle[i][j] != 0:
                    if cycle[i][j] > sum_/count_:
                        cycle[i][j] -= 1
                    elif cycle[i][j] < sum_/count_:
                        cycle[i][j] += 1
                        
    #있다면 new_cycle에 저장된걸로 갱신                    
    else:
        cycle = deepcopy(new_cycle)
    
    
    
result = 0

for i in range(n):
    for j in range(m):
        result += cycle[i][j]
        
print(result)