from collections import defaultdict
def fill_black(board, h, w):
board[h][w] = (-1 if h == 0 or board[h - 1][w] == -1 else 0)
def check(block, blocks, board) :
if len(blocks) < 4 : return False
h_list = sorted([h for h, w in blocks])
w_list = sorted([w for h, w in blocks])
for h in range(h_list[0], h_list[-1] + 1):
if any(color not in (-1, block) for color in board[h][w_list[0]:w_list[-1] + 1]):
return False
return True
def solution(board):
blocks = defaultdict(list)
answer = 0
for h in range((n := len(board))) :
for w in range(n) :
if (block := board[h][w]) > 0 :
(block_points := blocks[block]).append((h, w))
if not check(block, block_points, board) :
continue
answer += 1
for bh, bw in block_points :
fill_black(board, bh, bw)
elif block == 0 :
fill_black(board, h, w)
return answer
알고리즘
단순 구현 문제이기 때문에 특정 알고리즘은 필요없다.
board[h][w]가 빈칸인 경우
board[h-1][w]이 검은블록(-1) 일 경우에 검은블록으로 채운다- 검은블록은
board위에서 부터 차례대로 채워내려가기 때문에, 위에 검은블록인지 아닌지를 가지고 중간에 도형으로 막혀있는지 체크도 가능하다.
board[h][w]가 블록으로 채워져 있는 경우
blocks사전에 같은 색 블록들의 좌표들을 모은다.
- 같은 색 블록 좌표 4개가 모두 모이면 터트릴 수 있는지 없는지 확인
- 블록의 빈공간이 없다면 터트릴 수 있음
- 터트리고 나머지칸 전부 검은블록으로채움
- 블록의 빈공간이 있으면 못터트림
from collections import defaultdict
def fill_black(board, h, w):
board[h][w] = (-1 if h == 0 or board[h - 1][w] == -1 else 0)
def check(block, blocks, board) :
if len(blocks) < 4 : return False # 블록좌표가 4개가아니라면 pass
h_list = sorted([h for h, w in blocks]) # 블록의 h 좌표 최대, 최소값 구하기위해 정렬
w_list = sorted([w for h, w in blocks]) # 블록의 w 좌표 최대, 최소값 구하기위해 정렬
for h in range(h_list[0], h_list[-1] + 1): # 전체 블록의 영역에 빈칸이있는지 없는지 확인
if any(color not in (-1, block) for color in board[h][w_list[0]:w_list[-1] + 1]):
return False
return True
def solution(board):
blocks = defaultdict(list)
answer = 0
for h in range((n := len(board))) :
for w in range(n) :
if (block := board[h][w]) > 0 : # 블록인 경우
(block_points := blocks[block]).append((h, w)) # 블록좌표 사전에 추가
if not check(block, block_points, board) : # 터트릴 수 있는지 체크
continue
answer += 1
for bh, bw in block_points : # 터트린 블록 자리 검은블록으로 채움
fill_black(board, bh, bw)
elif block == 0 : # 빈칸인 경우
fill_black(board, h, w)
return answer