[BOJ] 17822. 원판 돌리기 (🥇, 구현/시뮬레이션)

🔗

풀이

시뮬레이션 과정을 크게 3가지로 분류할 수 있다

1. 원판 회전 (rotate)
2. 원판에 남아 있는 수
   2-1. 남아 있으면 : 서로 인접하면서 같은 수 모두 0
   2-2. x : 평균 구하고 평균보다 큰 수 -1, 작은 수 +1

원판을 회전 한 후, 원판에 남아 있는 수를 확인한다. 원판에 남아 있는 수의 합과 수의 개수는 total_num 에 배열 형태로 저장한다. 수의 개수가 0이면 바로 break 를 해서 0으로 나뉘는 불상사가 발생하지 않도록 한다. 다만 해당 과정은 원판 회전 직후가 아니라 수가 사라지는 이후의 과정을 수행한 후 확인한다.

find를 통해 너비 우선 탐색을 수행해 인접한 수들을 찾는다. 인접한 수가 하나도 없다면 remove_list 의 길이가 0이 된다. 만약 길이가 0이 아니라면 인접한 수가 존재하는 것이므로 해당하는 값들을 0으로 만들고 total_num 의 값들도 업데이트한다. 존재하지 않는다면 평균 값을 구하고 +1, -1을 한다. 이때 가장 최소로 가질 수 있는 값은 1이기 때문에 평균의 최소값은 1이 된다. 어차피 1보다 작은 값은 존재하지 않는 것으로 치기 때문에 -1 해주는 2-2 과정에서 수가 사라지는 경우는 없다.

이제 remove 과정을 통해 삭제된 값들이 존재하기 때문에 total_num 값을 확인해서 원판에 모든 수가 존재하는지 확인한다. 수가 하나라도 존재하면 과정을 이어가고 수가 0이 되면 break를 한다.

# 원판 돌리기

def rotate(i, d, k):
    k %= M
    if d == 0:
        k *= -1
    circle[i] = circle[i][k:] + circle[i][:k] 

def find(t): # 인접한 수 찾기
    remove_list = list()

    for i in range(N):
        for j in range(M):
            if visited[i][j] != t and circle[i][j]:
                visited[i][j] = t
                tmp = [(i, j)]
                queue = [(i, j)]
                while queue:
                    ii, jj = queue.pop(0)
                    for di, dj in (ii+1, jj), (ii-1, jj), (ii, (jj+1)%M), (ii, (jj-1)%M):
                        if di < 0 or dj < 0 or di >= N or dj >= M or visited[di][dj] == t or circle[di][dj] != circle[ii][jj]:
                            continue
                    
                        visited[di][dj] = t
                        tmp.append((di, dj))
                        queue.append((di, dj))
                if len(tmp) > 1:
                    remove_list.extend(tmp[:])

    return remove_list

def remove(remove_list):
    global total_sum
    for i, j in remove_list:
        total_sum[0] -= circle[i][j]         
        total_sum[1] -= 1        
        circle[i][j] = 0

def avg():
    avg_sum = total_sum[0] / total_sum[1]
    for i in range(N):
        for j in range(M):
            if circle[i][j] == 0:
                continue
            
            if circle[i][j] > avg_sum:
                circle[i][j] -= 1
                total_sum[0] -= 1
            elif circle[i][j] < avg_sum:
                circle[i][j] += 1
                total_sum[0] += 1

N, M, T = map(int, input().split())
circle = [list(map(int, input().split())) for _ in range(N)]
total_sum = [sum([sum(row) for row in circle]), N*M]
visited = [[0] * M for _ in range(N)]

for t in range(1, T+1):
    x, d, k = map(int, input().split())

    for i in range(x, N+1, x):
        rotate(i-1, d, k)
    
    remove_list = find(t)
    if len(remove_list) != 0:
        remove(remove_list)
    else:
        avg()
    
    if total_sum[1] == 0:
        break

print(total_sum[0])