백준: 17822 원판 돌리기

문제

17822번: 원판 돌리기

 

문제 풀이

 원판이 주어질 때, 원판은 서로 겹쳐져 있다. 이때, 원판을 명령어 때라 회전하고 인접한 수가 같은 수인 경우 제거하는 방식을 취한다. 그 후, 명령을 수행 후 최종적으로 원판에 남은 수를 합하여 출력하면 문제의 답을 찾을 수 있다.

 

 문제를 풀면서 주의할 점은 다음과 같다. 인접한 수를 제거하면 되고, 예제만 보고 나서 대충 풀어서 이상한 곳에서 또 헤매다가 시간을 보냈다.

1. x, d, k가 주어지면 원판 중 x의 배수인 경우 다 같이 회전한다.
2. 인접한 수가 하나도 없는 경우, 현재 원판에 적힌 수의 평균보다 작은 경우 1을 더하고 큰 경우 1을 뺀다.
   • `q[r][c] += 1 if q[r][c] < avg else -1`과 같이 최초에 코드를 작성하였다.
   • 이는 반대의 경우 `>=` 이기에, 예제 입력 5에서 오답을 출력하게 된다.

 나머지는 문제에 주어진 조건 대로 그대로 구현하면, 쉽게 답을 구할 수 있다. 원판을 회전시키기 위해서는 `deque`의 `rotate`를 활용하였다. 시계 방향(Clockwise)은 1 * K만큼 rotate 하고, 반시계 방향(Anti-Clockwise)은 -1 * K 만큼 rotate 하면 된다.

 

코드

from sys import stdin
from collections import deque


def del_adj_nums():
    for x, d, k in query:
        for i in range(N):
            # x의 배수가 되는 원판을 회전
            if (i + 1) % x == 0:
                q[i].rotate(change_dir[d] * k)

        temp = []
        # 다른 원판의 인접한 숫자 체크
        for r in range(N - 1):
            for c in range(M):
                if q[r][c] == q[r + 1][c] and q[r][c]:
                    temp += ([r, c], [r + 1, c])
        # 같은 원판에 인접한 숫자 체크
        for r in range(N):
            for c in range(M):
                if q[r][c - 1] == q[r][c] and q[r][c - 1]:
                    temp += ([r, c - 1], [r, c])
        
        # 인접한 것 중 동일한 숫자를 모두 0으로 만듦
        for r, c in temp:
            q[r][c] = 0

        # 회전 후 인접하는 것이 없는 경우, 평균에 따라 값을 변화 시킴
        if not temp:
            zero_cnt = sum([q[i].count(0) for i in range(N)])
            cnt = N * M - zero_cnt
            cur_sum = sum(sum(q, deque()))
            if not cnt:
                continue

            avg = cur_sum / cnt
            for r in range(N):
                for c in range(M):
                    if not q[r][c]:
                        continue

                    if q[r][c] > avg:
                        q[r][c] -= 1
                    elif q[r][c] < avg:
                        q[r][c] += 1


if __name__ == '__main__':
    change_dir = {0: 1, 1: -1}
    N, M, T = map(int, input().split())
    q = deque()
    for _ in range(N):
        q.append(deque(map(int, input().split())))

    query = [list(map(int, stdin.readline().split())) for _ in range(T)]

    del_adj_nums()
    print(sum(sum(q, deque())))