백준 구현 대비 상어 중학교

문제 : https://www.acmicpc.net/problem/21609

도식화

도식화 과정은 문제에서 제공한대로 진행하였다.
가장 큰 블록 찾기 -> 제거 후 점수 추가 -> 중력 작용 -> 90도 반시계 회전 -> 다시 또 중력 작용
위 과정을 블록을 찾을 수 없을때 까지 반복하면 된다.

코드로 구현하면 대충 다음과 같은 형태가 나타날것.

while True:
	biggest_block = find_biggest_block(graph)
    if not biggest_block:
    	break
    add_point(biggest_block)
    gravity(graph)
    rotate_90(graph)
    gravity(graph)
    대충 이런 형태로 작성이 될것

기존 구현 코드

from collections import deque
# 비어있는 칸을 empty라고 하자
# 검은색 -1 무지개 0 일반은 1이상 m이하
def gravity(graph):
  for i in range(n-1,-1,-1):
    for j in range(n):
      if graph[i][j]==-1:
        continue
      ci,cj=i,j
      while 0<=ci+1<n and graph[ci+1][cj]=='empty':
        graph[ci][cj], graph[ci+1][cj] = graph[ci+1][cj],graph[ci][cj]
        ci+=1

def find_biggest_block(graph):
  global point
  visited=[[0 for i in range(n)] for j in range(n)]
  place=None
  maxcount=1
  maxrainbow=0
  queue=deque()
  for i in range(n):
    for j in range(n):
      zerolist=[]

      if graph[i][j]!='empty' and graph[i][j]>0 and visited[i][j]==0:
        tempqueue=deque()
        tempqueue.append([i,j])
        queue.append([i,j])
        color=graph[i][j]
        visited[i][j]=1
        count=1
        rainbow=0
        while queue:
          ci,cj=queue.popleft()
          
          for mo in movelist:
            ni,nj=ci+mo[0],cj+mo[1]
            if 0<=ni<n and 0<=nj<n and (graph[ni][nj]==color or graph[ni][nj]==0) and visited[ni][nj]==0:
              visited[ni][nj]=1

              if graph[ni][nj]==0:
                zerolist.append([ni,nj])
                rainbow+=1
              count+=1
              queue.append([ni,nj])
              tempqueue.append([ni,nj])
        
        if count>maxcount:
          place=tempqueue
          maxcount=count
          maxrainbow=rainbow
        elif count==maxcount:
          if rainbow<maxrainbow:
            continue
          else:
            place=tempqueue
            maxcount=count
            maxrainbow=rainbow
      for ze in zerolist:
        visited[ze[0]][ze[1]]=0

  if maxcount<=1:
    return False

  for te in place:
    graph[te[0]][te[1]]='empty'
  point+=maxcount**2
  return True
  
def rotate():
  global graph
  new_graph=[[0 for i in range(n)] for j in  range(n)]
  for i in range(n):
    for j in range(n):
      new_graph[n-j-1][i]=graph[i][j]
  graph=new_graph

movelist=[[1,0], [0,1], [-1,0], [0,-1]]
n,m=map(int,input().split())
graph=[list(map(int,input().split())) for i in range(n)]
point=0


while find_biggest_block(graph):
  gravity(graph)
  rotate()
  gravity(graph)

print(point)

전체 코드를 구현하는 시간은 1시간 정도로 오래 걸리진 않았으나, 예제는 계속해서 통과하는데 실제 제출하면 1~2% 에서 계속해서 문제가 발생하였음. 디버깅하는데 총 이틀걸림 ㅠ.. 계속해서 문제가 발생한 이유는 다음 코드 때문이었다.

elif count==maxcount:
	if rainbow<maxrainbow:
    	continue
for ze in zerolist:
	visited[ze[0]][ze[1]]=0

continue 때문에 밑에있는 코드가 실행되지 않고 바로 다음 반복문을 실행해버림..

수정된 코드

from collections import deque
# 비어있는 칸을 empty라고 하자
# 검은색 -1 무지개 0 일반은 1이상 m이하
def gravity(graph):
  for i in range(n-1,-1,-1):
    for j in range(n):
      if graph[i][j]==-1:
        continue
      ci,cj=i,j
      while 0<=ci+1<n and graph[ci+1][cj]=='empty':
        graph[ci][cj], graph[ci+1][cj] = graph[ci+1][cj],graph[ci][cj]
        ci+=1



def find_biggest_block(graph):
  global point
  visited=[[0 for i in range(n)] for j in range(n)]
  maxcount=1
  queue=deque()
  answerlist=[]
  for i in range(n):
    for j in range(n):
      zerolist=[]
      if graph[i][j]!='empty' and graph[i][j]>0 and visited[i][j]==0:
        tempqueue=deque()
        tempqueue.append([i,j])
        queue.append([i,j])
        color=graph[i][j]
        visited[i][j]=1
        count=1
        rainbow=0
        while queue:
          ci,cj=queue.popleft()
          
          for mo in movelist:
            ni,nj=ci+mo[0],cj+mo[1]
            if 0<=ni<n and 0<=nj<n and (graph[ni][nj]==color or graph[ni][nj]==0) and visited[ni][nj]==0:
              visited[ni][nj]=1

              if graph[ni][nj]==0:
                zerolist.append([ni,nj])
                rainbow+=1
              count+=1
              queue.append([ni,nj])
              tempqueue.append([ni,nj])
        if count>maxcount:
          answerlist=[[rainbow,i,j]]
          maxcount=count
        elif count==maxcount:
          answerlist.append([rainbow,i,j])
      for ze in zerolist:
        visited[ze[0]][ze[1]]=0

  if maxcount<=1:
    return False
  answerlist.sort(key=lambda x:(-x[0],-x[1],-x[2]))
  ci,cj=answerlist[0][1],answerlist[0][2]
  visited=[[0 for i in range(n)] for j in range(n)]
  visited[ci][cj]=1
  color=graph[ci][cj]
  Q=deque()
  Q.append([ci,cj])
  graph[ci][cj]='empty'

  while Q:
    ci,cj=Q.popleft()
    for mo in movelist:
      ni,nj=ci+mo[0],cj+mo[1]
      if 0<=ni<n and 0<=nj<n and (graph[ni][nj]==0 or graph[ni][nj]==color) and visited[ni][nj]==0:
        graph[ni][nj]='empty'
        visited[ni][nj]=1
        Q.append([ni,nj])
  point+=maxcount**2
  return True
  
def rotate():
  global graph
  new_graph=[[0 for i in range(n)] for j in  range(n)]
  for i in range(n):
    for j in range(n):
      new_graph[n-j-1][i]=graph[i][j]
  graph=new_graph

movelist=[[1,0], [0,1], [-1,0], [0,-1]]
n,m=map(int,input().split())
graph=[list(map(int,input().split())) for i in range(n)]
point=0

while find_biggest_block(graph):
  gravity(graph)
  rotate()
  gravity(graph)

print(point)

추가

기존에 내가 구현했던 rotate 함수는 다음과 같았다.

def rotate(graph):
  new_graph=[[0 for i in range(n)] for j in  range(n)]
  for i in range(n):
    for j in range(n):
      new_graph[n-j-1][i]=graph[i][j]
  graph=new_graph

매개변수로 전달된 graph의 값이 변화하는 것을 기대했지만 graph의 값은 그대로였음, 이유는 당연하고도 단순했는데 매개변수 graph는 해당 함수 내부에서만 유효하며 함수가 종료되면 사라짐. 즉 함수 외부에서 선언된 진짜 graph의 값은 그대로 일 수 밖에 없음. 기초적인거 실수 안하도록 유의해야할듯

함수 외부의 graph값을 변경하려면 코드를 다음과 같이 수정해주어야 한다.

graph=[어쩌구]
def rotate(graph):
  new_graph=[[0 for i in range(n)] for j in  range(n)]
  for i in range(n):
    for j in range(n):
      new_graph[n-j-1][i]=graph[i][j]
  return newgraph
graph=rotate(graph)