[알고리즘 문제] 회전탑 (Python / 파이썬)

문제

N개의 층에 각각 M개의 숫자가 쓰여있다. 회전탑은 층에 존재하는 숫자를 회전시킬 수 있다. 회전 후 인접한 부분의 숫자가 같을 경우 회전판에서 숫자를 지운다.

[그림 1]

회전탑의 회전은 시계 방향 혹은 반시계 방향으로 가능하다. 한 번 회전시 회전되는 층은 다수가 될 수 있다. 
회전시켜야할 층의 번호와 배수관계에 있는 회전판들은 모두 회전된다. 또한, 회전은 동시에 일어난다.
 층을 회전한 뒤 회전한 어떠한 층에서도 지워지는 숫자가 없을 경우, 모든 층에 존재하는 숫자들의 평균을 구해 각각의 숫자와 비교한다.(평균값의 소숫점 아래는 버린다) 만약 평균보다 크면 -1을, 평균보다 작으면 +1을 더해준다. 앞서 말한 처리를 한 다음엔 다시 제거가 일어나는 것이 아닌 다음 회전이 일어난다.

[그림 2]

[그림 3]

회전탑의 정보와 회전시키는 정보가 주어졌을때, 회전을 마친 뒤 탑에 남아있는 숫자들의 합을 구해보자.

입력

첫 번째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 줄부터 T개의 테스트 케이스에 대한 정보가 주어진다.
각각의 테스트 케이스의 첫 번째 줄에 회전판의 개수 N, 각각의 회전판에 쓰여진 숫자 개수 M, 회전 횟수 K가 공백을 통해 구분하여 주어진다.
두 번째 줄부터 N개의 줄에 걸쳐 1층부터 N층까지 각 층의 회전판에 쓰여진 숫자가 공백을 통해 구분하여 주어진다. 주어진 순서대로 인접해있으며, 첫 번째 숫자가 12시 방향의 바로 오른쪽에 적힌다. 회전판에 적히는 숫자는 100을 넘지않는 자연수다.
바로 다음 줄부터 K개의 줄에 걸쳐 회전 정보가 공백을 통해 구분하여 주어진다. 각 줄에 주어지는 회전 정보는 회전시킬 층의 번호 a, 방향 d, 회전시킬 칸 수 c 순서로 주어진다. 회전 방향은 0과 1로 주어지며, 0은 시계 방향, 1은 반시계 방향이다. (3 ≤ N, M ≤ 50, 1 ≤ K ≤ 50, 1 ≤ a ≤ N, 1 ≤ c ≤ 50)

출력

각 테스트 케이스에 대해 회전을 마친 뒤 회전탑에 남은 숫자들의 합을 출력한다. 각 테스트 케이스의 출력 양식은 "#t r"이다. t는 테스트 케이스의 번호이며, 1부터 시작한다. r은 문제에 대한 결과값을 뜻한다.

---

문제 풀이

문제를 처음 접했을 때 층을 회전시켜야 한다는 점과,

인접한 원소를 삭제해야 한다는 점을 어떻게 구현해야 할지 어려움으로 다가왔다.

그래서 구현해야 할 것들을 하나씩 차근차근 정리하며 생각해보았다. 

 

먼저, 전체적인 단계는 층 회전 -> 인접한 같은 원소 삭제 -> 삭제할게 없으면 평균처리 이다. 

따라서 이 단계에 따라 세부적으로 단계를 나누어 단계마다 유의해야 할 점을 정리해보았다.

1. 층의 배수층이 함께 회전된다. 

- 층을 입력 받을 때 1부터 입력받아야 한다.

2. 행이 시계방향 혹은 반시계 방향으로 회전한다.

- % 연산을 사용할 것이므로 0부터 입력받을 것이다.

- 회전 할 때 원소를 하나씩 이동시키면 원본이 훼손된다. 따라서 임시로 배열을 만들어야 한다.

3. 지울 때 인접한 곳에 같은게 있으면 지운다. 

- 인접한 곳 = 상하좌우로 인접한 곳

- 상하좌우로 탐색할 때 좌/우 방향은 범위를 벗어나도 된다. (마찬가지로 % 연산 사용)

- 이때, 주의해야할 점은 하나씩 지워나가면 인접한 같은 원소를 모두 판단할 수 없다.

- 지워야할 위치를 모두 표시해둔 뒤 나중에 한꺼번에 지워야 한다. 

- 0인 위치는 이미 삭제한 위치이다. 따라서 0일 경우를 항상 고려해줘야 한다. 

4. 만약 삭제할 원소가 하나도 없다면 평균을 구해 조건에 따라 처리해준다. 

- 모든 원소가 이미 0이라면 종료해준다.

- 조건에 따라 처리해줄 때, 0은 넘어가도록 해준다. 

5. 위의 과정을 k번 수행한 뒤 남은 원소들의 총 합을 구해준다.  

 

정리해 둔 단계에 따라 구현을 하면 쉽게 답을 출력할 수 있다. 

---

My Code

# 층을 회전시키는 함수
def rotate(idx, dir, dist):
    temp = [0] * 60 # 회전 결과를 저장할 임시 배열

    if dir == 0: # 시계 방향 
        for i in range(m):
            temp[i] = array[idx][(i - dist) % m] # 오른쪽으로 이동
    else:        # 반시계 방향
        for i in range(m):
            temp[i] = array[idx][(i + dist) % m] # 왼쪽으로 이동
    
    for i in range(m):
        array[idx][i] = temp[i] # 저장해둔 결과를 원본에 넣어줌

# 상하좌우로 탐색할 방향 변수
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 인접한 곳에 같은 원소가 있으면 지워주는 함수
def erase():
    check = [[False] * 60 for _ in range(60)] # 지울 원소인지 표시해둘 배열
    flag = False # 지울 원소가 있었는지 알려줄 변수
    for i in range(1, n + 1):
        for j in range(m):
            if array[i][j] == 0: continue # 0이라면 넘어감
            for k in range(4): # 상하좌우로 탐색
                nx = i + dx[k]
                ny = (j + dy[k]) % m # 좌/우는 범위를 벗어나도 됨
                if 1 <= nx <= n: # 층 범위 안에서
                    if array[nx][ny] == array[i][j]: # 같은 원소라면
                        check[i][j] = True # 해당 원소를 지워야 한다고 표시
                        flag = True # 지울 원소가 있었다고 표시

    for i in range(1, n + 1):
        for j in range(m):
            if check[i][j]: # 지워야 하는 원소이면
                array[i][j] = 0 # 지워줌

    return flag # 지울 원소가 있었는지 알려주기 위해 반환

# 평균을 구해 조건에 따라 처리해줄 함수
def get_avg():
    sum_value = 0 
    count = 0 
    for i in range(1, n + 1):
        for j in range(m):
            if array[i][j] > 0: # 0보다 크다면
                sum_value += array[i][j] # 모두 더해줌
                count += 1               # 더한 것의 개수를 세어줌
    
    if count == 0: return # count가 0이면 모두 0이라는 것이므로 종료

    avg = sum_value // count # 더한 결과에 개수를 나눈 몫 = 평균
    for i in range(1, n + 1):
        for j in range(m):
            if array[i][j] == 0: continue # 0이면 넘어감
            if array[i][j] < avg: array[i][j] += 1 # 평균보다 작으면 1더해줌
            elif array[i][j] > avg: array[i][j] -= 1 # 평균보다 크면 1빼줌

for tc in range(int(input())):
    n, m, k = map(int, input().split()) # 회전판의 개수, 회전판에 쓰여진 숫자 개수, 회전 횟수

    # 회전판에 쓰여진 숫자 정보 
    array = [[0] * m for _ in range(n + 1)]
    for i in range(1, n + 1):
        arr = list(map(int,input().split()))
        for j in range(m):
            array[i][j] = arr[j]

    for _ in range(k):
        a, b, c = map(int,input().split()) # 회전 층 번호, 방향, 회전시킬 칸 수

        for i in range(a, n + 1, a): # 회전 층의 배수층을 모두 회전
            rotate(i, b, c)
        
        if not erase(): # 만약 지울 원소가 없다면
            get_avg()   # 평균 처리

    # 회전이 모두 끝난 뒤 남은 원소들의 총합 구해줌
    sum_value = 0
    for i in range(1, n + 1):
        for j in range(m):
            sum_value += array[i][j]

    print('#' + str(tc + 1), end = ' ')
    print(sum_value)