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

문제 링크:

문제 이해

---

• N개의 원판이 크기 순서대로 겹쳐져 있고, 각각의 원판에는 M개의 정수가 적혀있다(위치: (i, j)).
• 번호가 x의 배수인 원판을 d방향(0: 시계방향, 1: 반시계방향)으로 k칸 회전시킨다.
• 각각의 원판은 독립적으로 회전한다. 회전 후 인접하면서 수가 같은 것을 모두 찾아 아래 조건을 통해 숫자를 삭제시킨다(숫자가 남아있는 경우에).
  • 인접하면서 같은 수가 있는 경우에는 원판에서 해당 수를 모두 지운다.
  • 없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.

원판 예시(N=3, M=4)

• 최종적으로 구해야 하는 것: 원판을 T번 회전시킨 후에 원판에 적힌 수의 합
• 중간 과정으로 구해야 하는 것:
  • 회전 조건에 따른 원판 회전 후 상태
  • 회전 후 인접한 수에 따른 원판 원소 업데이트
    
    
    
    
    
    

해결 전략

---

1. 회전할 원판 정하기 (x의 배수인 원판)
2. 회전할 원판 내의 모든 원소 회전
3. 각 원소에서 4방으로 인접 원소와 비교(인접 원소 같은 경우 탐색), 삭제
4. 삭제되지 않은 경우 해당 판의 원소 평균 구하고 +1 or -1
   
   
   
   
   
   

구현 코드, 풀이

---

def rotate_board(board, x, d, k):
    def rotate(k):
        if d == 0:
            board[i] = board[i][::-1]

        for _ in range(k):
            tmp = board[i][0]
            for j in range(M):
                if j + 1 == M:
                    continue
                board[i][j] = board[i][j + 1]
            board[i][-1] = tmp

        if d == 0:
            board[i] = board[i][::-1]

    # 이동할 원판 정하기
    for i in range(N):
        tmp_list = []
        # x의 배수에 대해 동작할 것
        if (i + 1) % x == 0:
            rotate(k)

    return board

def calculate(board):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    cnt = 0
    rm_num = 0
    same_point = []
    for i in range(N):
        for j in range(M):
            if board[i][j] == 0:
                rm_num += 1
                continue
                
            for m in range(4):
                nx, ny = i + dx[m], j + dy[m]
                if nx < 0 or nx >= N:
                    continue
                elif ny == M:
                    ny = 0
                elif ny == -1:
                    ny = M-1
                if board[i][j] == board[nx][ny]:
                    same_point.append([i,j])
                    cnt += 1
                    continue

    if cnt > 0:
        for x, y in same_point:
            board[x][y] = 0
    elif rm_num == N * M:
        return board
    else:
        avg = sum([sum(board[i]) for i in range(N)]) / (N*M - rm_num)

        for i in range(N):
            for j in range(M):
                if board[i][j] == 0:
                    continue

                if board[i][j] > avg:
                    board[i][j] = board[i][j] - 1
                elif board[i][j] < avg:
                    board[i][j] = board[i][j] + 1
                else:
                    continue
    return board

N, M, T = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
x, d, k = [], [], []
for i in range(T):
		xt, dt, kt = map(int, input().split())
		x.append(xt)
		d.append(dt)
		k.append(kt)

		
if __name__ == '__main__':
		
		for i in range(T):
		    # 원판 회전
		    board = rotate_board(board, x[i], d[i], k[i])
		    # 수 계산
		    board = calculate(board)
		
		print(sum([sum(board[i]) for i in range(N)]))

1. main 블록:
   • 초기 입력으로 원판의 크기와 회전할 횟수, 원판의 숫자에 대한 정보를 입력받는다.
   • 각 회전 T번에 대해 rotate_board와 calculate 함수를 호출하여 원판을 회전하고 수를 계산한다.
   • 최종적으로 남은 수들의 합을 출력한다.
2. rotate_board 함수:
   • board 행렬에서 x의 배수에 해당하는 원판에 대해서만 회전을 수행한다(rotate 함수).
   • rotate는 원판을 회전시키는 역할을 한다.
     • 회전 방향d에 따라서 원판을 뒤집은 후, 회전할 칸 수k만큼 회전시킨다.
3. calculate 함수:
   • board는 회전한 후의 원판 상태를 나타낸다.
   • 상하좌우 네 방향으로 이웃한 수가 같은지 확인하고, 같다면 same_point 리스트에 해당 좌표를 추가한다(이 때, 행렬의 0번과 -1번 원소의 이웃함에 대해 주의).
   • 만약 same_point 리스트가 비어있다면, 모든 수가 같은 것이므로 이동을 하지 않고 그대로 반환한다.
   • 같은 수가 있는 경우, 해당 좌표의 수를 0으로 만든다.
   • 같은 수가 없는 경우, 모든 수의 평균을 구한 후, 평균보다 큰 수는 1을 빼고, 작은 수는 1을 더한다.
   • board를 반환한다.