[백준 23291번] 어항 정리 (Python3)

import sys
input = sys.stdin.readline
dy = [1,0,-1,0]
dx = [0,1,0,-1]

def roll():
  global fishbowl
  h = len(fishbowl)
  if h==1:
    w = 1
  else:
    w = len(fishbowl[-1])
  if len(fishbowl[0])-w < h:
    return False
  newfishbowl = [[0]*h for i in range(w+1)]
  newfishbowl[0] = fishbowl[0][w:]
  for y in range(h):
    for x in range(w):
      newfishbowl[w-x][y] = fishbowl[y][x]
  fishbowl = newfishbowl
  return True

def distribute():
  List = []
  for y in range(len(fishbowl)):
    for x in range(len(fishbowl[y])):
      for i in range(2):
        y1,x1 = y+dy[i],x+dx[i]
        try:
          diff = fishbowl[y][x]-fishbowl[y1][x1]
        except:
          continue
        if diff >= 5:
          diff //= 5
        elif diff <= -5:
          diff = -(abs(diff)//5)
        else:
          continue
        List.append((y,x,diff))
        List.append((y1,x1,-diff))
  for y,x,diff in List:
    fishbowl[y][x] -= diff

def organize():
  global fishbowl
  newfishbowl = []
  for x in range(len(fishbowl[0])):
    for y in range(len(fishbowl)):
      try:
        newfishbowl.append(fishbowl[y][x])
      except:
        continue
  fishbowl = [newfishbowl]

def fold():
  global fishbowl
  newfishbowl = []
  newfishbowl.append(fishbowl[0][N//2:])
  newfishbowl.append([*reversed(fishbowl[0][:N//2])])  
  fishbowl = newfishbowl

  newfishbowl = []
  newfishbowl.append(fishbowl[0][N//4:])
  newfishbowl.append(fishbowl[1][N//4:])  
  newfishbowl.append([*reversed(fishbowl[1][:N//4])])
  newfishbowl.append([*reversed(fishbowl[0][:N//4])])
  fishbowl = newfishbowl

N,K = map(int,input().split())
fishbowl = [[*map(int,input().split())]]

cnt = 0
while True:
  finish = True
  Min = min(fishbowl[0])      #1번과정
  for i in range(N):
    if fishbowl[0][i] == Min:
      fishbowl[0][i] += 1
    else:
      if fishbowl[0][i]-Min > K:
        finish = False
  if finish:
    break
  while roll():              #2번과정
    continue    
  distribute()            #3번과정
  organize()              #4번과정
  fold()                  #5번과정
  distribute()            #6번과정
  organize()              #7번과정  
  cnt += 1

print(cnt)

구현량이 어마어마한 문제이다.

코드에서도 볼 수 있듯이 문제에서 요구하는 처리과정만 7개가 된다.

 

하지만 각 과정을 하나하나 떼어놓고 보면 어려울만한건 한개도 없고, 테스트케이스가 친절하게 나와있기 때문에 시간이 소요될 뿐 매우 쉽게 풀 수 있다.

 

단순 노가다 구현인데 플래티넘이라는 점에서 큐빙 [백준 5373번] 큐빙 (Python3) (tistory.com) 과 비슷하다.

 

 

알고리즘은 어려울게 하나도 없기 때문에 따로 설명할 만한건 없고, 풀면서 알게된 팁을 몇 가지 말하자면,

1. 처음부터 어항을 이중리스트로 만드는 것이 좋다. len(fishbowl)로 높이를 알아야하므로

2. 어항의 각 층이 너비가 다르기 때문에 인덱스 예외처리를 굳이 하나하나 조건을 나누기보다는 try,except라는 무적함수를 사용해주면 쉽게 풀 수 있다.

3. 이때 2번에서 주의해야할 점은 인덱스가 음수값이어도 try함수가 오류가 안나기 때문에 (-1인덱스가 가능하므로) + 방향으로만 탐사하는것이 좋다.

4. 3번 과정과 6번 과정에서 차이를 5로 나눈 몫을 구할 때 차이값이 음수인지 양수인지를 구분해주어야한다. (음수를 나누면 몫이 1 작아질 수 있다)

5. 구현해야할 과정이 매우 많기 때문에 코드를 처음부터 끝까지 다 짠다음 디버깅을 하기보다 매 과정마다 디버깅을 끝내고 넘어가는 것이 좋다. 테스트케이스가 매우 친절하다.

 

 

오늘의 교훈) 음수의 몫과 양수의 몫을 주의하자