문제 : 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)