생각 흐름
- 이게 뭔 문제지? 4단계???
- 진정하고 생각해보니 너무 쉬운 문제일 수도...
- 블록을 회전하는 것도 아니고, 블록을 밑으로 내리는 것도 아니다.
- 완전한 직사각형이 된다는 것은 문제의 설명대로라면 아마 블록에서 빈 부분을 채우는 것을 의미한다. (모든 블록은 3x2 크기이며 두 개의 빈 칸이 뚫려있다고 생각하면 됨)
- 따라서 블록이 완전한 직사각형이 될 수 있다 -> 두 빈 칸이 채워질 수 있다 -> 빈 칸 위에 아무것도 없다
- 이렇게 쉬울 리가 없다. 혹시 완전탐색 문제는 아닐까?
- 아니다. 어떤 블록을 터뜨릴 때 그것은 다른 블록이 터지는 것을 돕기만 할 뿐, 방해하진 않는다. -> 즉 블록을 터뜨리는 순서가 미래의 결과에 영향을 미치지 않는다. 터뜨려질 수 있는 블록은 어떻게 하더라도 무조건 터지게 돼있다.
- 따라서 더 이상 터지는 블록이 없을 때까지 블록을 다 터뜨리면 된다.
풀이
블록에서 빈 칸을 찾으려면...
y축이나 x축 중 한 축은 같은 값이 (3번, 1번), 다른 축은 (2번, 1번, 1번) 나온다.
값이 3번 나오게 되는 축에서 나머지 1번 나오는 값과, 다른 축에서 1번 씩만 나오는 값들의 product 연산이 바로 빈 칸이다.
예를 들어 y축(a:3, b:1), x축(c:2, d:1, e:1)이라고 할 때
값이 3번 나오게 되는 축(y)에서 나머지 1번 나오는 값 = b,
다른 축(x)에서 1번 씩만 나오는 값들 = (d, e)
의 product 연산 => (b, d), (b, e) 가 바로 빈 칸이다.
이때 축을 잘 봐야 한다. 만약 b가 x축이었다면 (d, b), (e, b)였을 것이다.
코드
from collections import Counter, defaultdict
def solution(board):
global N
N = len(board)
pos = init_pos(board)
answer = 0
while True:
popped = pop_blocks(board, pos)
if popped == 0:
break
answer += popped
return answer
def init_pos(board):
pos = defaultdict(lambda: [])
for i in range(N):
for j in range(N):
if board[i][j] != 0:
pos[board[i][j]].append((i, j))
return pos
def get_blanks(blocks):
counts = [sorted(Counter([block[i] for block in blocks]).items(), key=lambda x: -x[1]) for i in range(2)]
target_idx = [i for i in range(2) if counts[i][0][1] == 3][0]
axis = counts[target_idx][1][0]
counter_idx = (target_idx + 1) % 2
counter_axis = [counts[counter_idx][i][0] for i in range(3) if counts[counter_idx][i][1] == 1]
blanks = []
for c in counter_axis:
temp = [0, 0]
temp[target_idx] = axis
temp[counter_idx] = c
blanks.append(temp)
return blanks
def is_fillable(board, blanks):
for blank in blanks:
for i in range(blank[0], -1, -1):
if board[i][blank[1]] != 0:
return False
return True
def pop_blocks(board, pos):
cnt = 0
popped = []
for n, p in pos.items():
blanks = get_blanks(p)
if is_fillable(board, blanks):
cnt += 1
for py, px in p:
board[py][px] = 0
popped.append(n)
for p in popped:
pos.pop(p)
return cnt
get_blanks 함수는 블록의 위치값 리스트를 넣어주면 블록을 반환한다.
y축과 x축에 구애받지 않고 한 번에 구할 수 있는 로직으로 작성하였다.
