백준 온라인 저지, 구현 / 17822번: 원판돌리기 (파이썬 / , 백준 골드문제, 삼성 SW 기출문제)

문제

반지름이 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번째 회전할때 사용하는 변수는 x_i, d_i, k_i이다.

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

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

입력

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

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

다음 T개의 줄에 x_i, d_i, k_i가 주어진다.

출력

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

제한

• 2 ≤ N, M ≤ 50
• 1 ≤ T ≤ 50
• 1 ≤ 원판에 적힌 수 ≤ 1,000
• 2 ≤ x_i ≤ N
• 0 ≤ d_i ≤ 1
• 1 ≤ k_i < M

예제 입력 1

4 4 1
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1

예제 출력 1

30

원판의 초기 상태는 다음과 같다.

x1 = 2, d1 = 0, k1 = 1 2번, 4번 원판을 시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 2

4 4 2
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3

예제 출력 2

22

예제 1에서 이어진다.

x2 = 3, d2 = 1, k2 = 3 3번 원판을 반시계 방향으로 3칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 3

4 4 3
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2

예제 출력 3

22

예제 2에서 이어진다.

x3 = 2, d3 = 0, k3 = 2 2, 4번 원판을 시계 방향으로 2칸 돌린 후	인접하면서 수가 같은 것이 없다. 따라서, 평균 22/6 보다 작은 수는 +1, 큰 수는 -1 했다.

예제 입력 4

4 4 4
1 1 2 3
5 2 4 2
3 1 3 5
2 1 3 2
2 0 1
3 1 3
2 0 2
3 1 1

예제 출력 4

0

예제 3에서 이어진다.

x4 = 3, d4 = 1, k4 = 1 3번 원판을 반시계 방향으로 1칸 돌린 후	인접하면서 수가 같은 것을 모두 지운 후

예제 입력 5

4 6 3
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9
2 1 4
3 0 1
2 1 2

예제 출력 5

26

힌트

접근 방법

- 0. 원판과 원판에 적힌 수를 이중 리스트로 입력받는다. 단, 원판을 입력받을 때 인덱스가 1부터 시작하도록 입력받는다.
- 1. 원판을 회전시키는 함수를 만든다.
- 1-1. 원판 내에 있는 숫자는 나머지 연산자를 활용해 인덱스를 이동한다.
- 2. 인접한 숫자를 제거하는 함수를 만든다.
- 2-1. 원판을 하나씩 탐색하며 원판 내에 있는 인접한 숫자는 나머지 연산자를 활용해 구한다.
- 2-2. 원판간의 인접한 숫자는 주어진 원판 개수 범위 내에 있는지 확인한 뒤, 인접한 숫자를 구한다.
- 2-3. 동일한 인접한 숫자가 있다면 인접한 숫자의 인덱스를 저장한다.
- 2-4. 인접한 숫자가 없는 경우엔 평균을 구한 뒤, 다시 한번 원판을 하나씩 탐색하며 값을 1씩 더하거나 뺀다.
- 3. 1번과 2번을 t번만큼 반복한 뒤, 원판에 남아있는 숫자를 출력한다.

코드

# https://www.acmicpc.net/problem/17822
# 접근 방법
# 0. 원판과 원판에 적힌 수를 이중 리스트로 입력받는다. 단, 원판을 입력받을 때 인덱스가 1부터 시작하도록 입력받는다.
# 1. 원판을 회전시키는 함수를 만든다.
# 1-1. 원판 내에 있는 숫자는 나머지 연산자를 활용해 인덱스를 이동한다.
# 2. 인접한 숫자를 제거하는 함수를 만든다.
# 2-1. 원판을 하나씩 탐색하며 원판 내에 있는 인접한 숫자는 나머지 연산자를 활용해 구한다.
# 2-2. 원판간의 인접한 숫자는 주어진 원판 개수 범위 내에 있는지 확인한 뒤, 인접한 숫자를 구한다.
# 2-3. 동일한 인접한 숫자가 있다면 인접한 숫자의 인덱스를 저장한다.
# 2-4. 인접한 숫자가 없는 경우엔 평균을 구한 뒤, 다시 한번 원판을 하나씩 탐색하며 값을 1씩 더하거나 뺀다.
# 3. 1번과 2번을 t번만큼 반복한 뒤, 원판에 남아있는 숫자를 출력한다.
def Rotate(array):
    # 1. 원판을 회전시키는 함수
    x, d, k = map(int, sys.stdin.readline().split())
    
    if d == 0: # 시계 방향
        for i in range(x, n+1, x):
            array[i] = [array[i][(j-k)%m] for j in range(m)]

    else: # 반시계 방향
        for i in range(x, n+1, x):
            array[i] = [array[i][(j+k)%m] for j in range(m)]

def Find_adjacent_number(array):
    # 2. 인접한 동일한 숫자를 찾는 함수
    adjacent_same_number = []
    total = 0
    count = 0
    for i in range(1, n+1):
        for j in range(m):
            if array[i][j]:
                # 원판 내 인접한 숫자 찾기
                if array[i][j] == array[i][(j+1)%m]:
                    adjacent_same_number.append([i, (j+1)%m])
                if array[i][j] == array[i][(j-1)%m]:
                    adjacent_same_number.append([i, (j-1)%m])
                
                # 원판 간의 인접한 숫자 찾기
                if 1 <= i - 1 and array[i][j] == array[i-1][j]:
                    adjacent_same_number.append([i-1, j])
                if i + 1 <= n and array[i][j] == array[i+1][j]:
                    adjacent_same_number.append([i+1, j])
                
                total += array[i][j]
                count += 1
    
    if adjacent_same_number: # 인접한 숫자가 있다면
        for i, j in adjacent_same_number:
            array[i][j] = 0

    else: # 인접한 숫자가 없다면 평균 값으로 1을 더하거나 뺀다.
        if count:
            average = total / count
            for i in range(1, n+1):
                for j in range(m):
                    if array[i][j]:
                        if array[i][j] > average:
                            array[i][j] -= 1
                        elif array[i][j] < average:
                            array[i][j] += 1
    
import sys
n, m, t = map(int, sys.stdin.readline().split())
array = [[]]
for _ in range(n):
    array.append(list(map(int, sys.stdin.readline().split()))) # array[원판 번호][원판 내 숫자 인덱스]

for rot in range(t):
    Rotate(array)
    Find_adjacent_number(array)

result = 0
for i in range(1, n+1):
    for j in range(m):
        result += array[i][j]

print(result)