[python] BOJ 백준 17822: 원판돌리기

1. 문제  

반지름이 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)

원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.

원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.

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

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

2. 입력   

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

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

다음 T개의 줄에 xi, di, ki가 주어진다.

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 원판을 회전시키면서 인접한 숫자들을 탐색해주고 조건에 맞게 처리하면된다. 원판을 회전시키는 것은 파이썬의 deque 라이브러리를 사용하여 rotate 함수를 써주면 쉽게 처리할 수 있다. 원판을 회전시켜준 후, 지울 좌표를 담아두는 remove_arr 빈 배열을 생성해주어 인접한 숫자가 같을 경우에 추가를 해주어야한다. 바로 적용하지 않는 이유는 인접한 숫자가 여러개가 같을 수 있기 때문이다. 같은원판끼리 , 다른 원판끼리 인접한 숫자를 탐색하며 0이 아니면서 숫자가 같은 경우에는 지울 좌표로 저장을 해준다. 나중에 지울 배열을 돌면서 인덱스에 해당하는 원판 좌표의 값은 0으로 만들어주면된다. 만약 지울 배열이 없으면 문제에서 평균을 구해주어야하는데, 이때 주의할 점은 평균을 구하는 개수에서 0의 개수는 빼주어야한다는 것이다. 이미 지워진 값은 평균값으로 들어가지 않기 때문이다. 평균을 구했으면 원판을 돌면서 +-1 을 해주면된다. 

 

5) 구현코드   

from collections import deque

n,m,T=map(int,input().split())
board=[deque(int(x) for x in input().split()) for _ in range(n)] #원판 
commands=[list(map(int, input().split())) for _ in range(T)] #명령 

#명령을 돌면서 
for t in range(T): 
  x,d,k=commands[t] #배수, 방향, 칸 
  sum_num=0 #원판에 적힌수의 합
  #원판을 돌면서  
  for i in range(n): 
    sum_num+=sum(board[i]) #원판의 합 
    if (i+1)%x==0: #x의 배수인 원판이라면 
      if d==0: #시계방향회전 
        board[i].rotate(k) #k만큼 
      else: #반시계방향회전 
        board[i].rotate(-k) #k만큼 

  if sum_num!=0: 
    remove_arr=[] #지울 숫자들 

    #원판을 돌면서 
    for i in range(n):
      for j in range(m):
        #비어있지 않은 것들중에
        if board[i][j]!=0 and board[i][j-1]!=0:
          #같은원판끼리 인접한 숫자들  지워주기 
          if board[i][j]==board[i][j-1]:
            remove_arr.append((i,j))
            remove_arr.append((i,j-1))
    #원판을돌면서 
    for j in range(m):
      for i in range(n-1):
        #비어있지 않은 것들중에 
        if board[i][j]!=0 and board[i+1][j]!=0:
          #다른원판끼리 인접한 숫자들 지워주기 
          if board[i][j]==board[i+1][j]:
            remove_arr.append((i,j))
            remove_arr.append((i+1,j))
    #배열에 있는 숫자를 동시에 지워주기
    for i,j in remove_arr:
      board[i][j]=0
    #만약 지울숫자가 없다면   
    if len(remove_arr)==0:
      s,zero=0,0 
      for i in range(n):
        s+=sum(board[i]) 
        zero+=board[i].count(0)
      avg=s/(n*m-zero) #평균 (0제외)

      for i in range(n):
        for j in range(m):
          if board[i][j]!=0 and board[i][j]>avg:
            board[i][j]-=1 #평균보다 작은수 -1
          elif board[i][j]!=0 and board[i][j]<avg:
            board[i][j]+=1 #평균보다 큰수 +1
  else: #원판에 있는 숫자가 모두 지워진 경우 
    break

result=0
#원판에 남은 숫자들의 합 
for i in range(n):
  result+=sum(board[i])
print(result)

 

⭐️난이도:  골드 3 ⭐️

https://www.acmicpc.net/problem/17822

17822번: 원판 돌리기