색깔 폭탄
Simulation, BFS
평균 : 180'
sol : 96' 36''
- 수행 시간 : 212ms
- 메모리 : 23MB
New Skills
- Easy. 수행 시간도 모범 답안과 매우 근사.
- vs 모범 답안
모범 답안에서는 BFS를 통해 폭탄 군집의 기준 좌표만 저장해두고, 마지막에 해당 좌표에서 bfs를 한 번 더 해주면서 해결했다. 이에 대해 내 답안과 비교해보면, 나는 매 bfs마다 좌표들을 전부 저장한다. 따라서 마지막에 bfs를 한 번 덜하게 되지만, 결과적으로 데이터셋이 매우 커질 경우 메모리 용량 초과 문제가 뜰 가능성이 높다. 모범 답안의 방식을 채택하자. 요약하자면 BFS로 최적 좌표 찾기 + 마지막에 BFS > 매번 BFS로 좌표들 갖고 다니기 시간 복잡도는 어쨌든 둘 다 공간복잡도 Θ(n⁴)까지 갈 수는 있지만, 내 코드가 상수항이 훨씬 더 커지므로 개선할 필요가 있다.
from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
STONE, RED, EMPTY = -1, 0, -2
def debug(board):
for r in board:
for c in r:
print(c, end=" ")
print()
print()
def bomb_exist():
for i in range(n):
for j in range(n):
if grid[i][j] >= 0:
return True
return False
def simulate():
score = 0
while bomb_exist():
area = find_max_area()
if len(area) >= 2:
bomb(area)
score += pow(len(area), 2)
else:
break
gravity()
rotate()
gravity()
return score
# find max area > min red > max row > min col
def find_max_area():
areas = []
for i in range(n):
for j in range(n):
# RED, STONE 제외
if grid[i][j] <= 0:
continue
areas.append(list(get_area_bfs(i, j)))
# max_area
areas.sort(key=lambda x: [[-x[1], x[2], -x[0][0], x[0][1]]])
return areas[0][3]
def inbound(i, j):
if 0 <= i < n and 0 <= j < n:
return True
return False
def get_area_bfs(i, j):
dis, djs = [0, 1, 0, -1], [1, 0, -1, 0]
q = deque()
visited = [
[False for _ in range(n)]
for _ in range(n)
]
area = [[i, j]]
red_area = []
cur_color = grid[i][j]
size = 1
red_count = 0
visited[i][j] = True
q.append((i, j))
while q:
ci, cj = q.popleft()
for di, dj in zip(dis, djs):
ni, nj = ci + di, cj + dj
if inbound(ni, nj) and not visited[ni][nj]:
# 같은 색이거나 red bomb면 군집 포함.
if grid[ni][nj] == cur_color or grid[ni][nj] == RED:
q.append((ni, nj))
visited[ni][nj] = True
size += 1
# red는 area에 명시적으로 추가하진 않음 for sort
if grid[ni][nj] == RED:
red_count += 1
red_area.append([ni, nj])
else:
area.append([ni, nj])
area.sort(key=lambda x: [-x[0], x[1]])
return area[0], size, red_count, area + red_area
def bomb(area):
for elem in area:
grid[elem[0]][elem[1]] = EMPTY
def gravity():
for col in range(n):
idx = n - 1
temp_col = [-2 for _ in range(n)]
for row in range(n-1, -1, -1):
if grid[row][col] == STONE:
temp_col[row] = grid[row][col]
idx = row - 1
continue
if grid[row][col] == EMPTY:
continue
else:
temp_col[idx] = grid[row][col]
idx -= 1
for row in range(n):
grid[row][col] = temp_col[row]
def rotate():
global grid
rot = [
[0 for _ in range(n)]
for _ in range(n)
]
for i in range(n):
for j in range(n):
rot[n - j - 1][i] = grid[i][j]
grid = [row[:] for row in rot]
return
##########################################################
print(simulate())