문제 보기 · Level 4 · 2019 KAKAO BLIND RECRUITMENT · 정답률 21% · 푼 사람 2,004명 (2026-09-30 기준)1
문제
N×N 보드에 1×1 칸 네 개로 된 블록들이 놓여 있다(세 종류를 돌려 만든 12가지 모양). 0은 빈칸이고 블록마다 번호가 다르다. 플레이어는 위에서 1×1 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록과 기존 블록을 합쳐 속이 꽉 찬 직사각형이 되면 그 블록을 없앨 수 있다. 없앨 수 있는 블록 수의 최댓값을 돌려준다.
- 4 ≤ N ≤ 50
- 블록 번호 1 ~ 200
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
구현과 시뮬레이션: “없앨 수 있는 블록을 찾아 없애기”를 더 없앨 것이 없을 때까지 되풀이한다. 블록마다 “직사각형이 되려면 채워야 할 빈칸”과 “그 빈칸에 위에서 떨어뜨릴 수 있나”를 확인한다.
1단계 · 작은 예로 손으로 풀기
ㄴ 모양 블록이 (1, 0), (2, 0), (2, 1), (2, 2)에 있다(행, 열). 이 블록을 감싸는 가장 작은 직사각형은 1 ~ 2행, 0 ~ 2열의 2×3 상자다. 상자에서 블록이 아닌 칸은 (1, 1), (1, 2) 두 칸이다.
- 두 칸이 비어 있고, 각 칸 위(0행)도 비어 있으면 검은 블록을 떨어뜨려 채울 수 있다. 그러면 2×3 직사각형이 되어 블록을 없앤다.
- 두 칸 중 하나 위에 다른 블록이 있으면 떨어뜨린 검은 블록이 거기 걸린다. 지금은 못 없앤다. 그 블록이 먼저 없어지면 나중에 될 수 있다.
2단계 · 가장 단순한 방법과 그 속도
검은 블록을 어느 열에 몇 개 떨어뜨릴지 모두 해 보면 가짓수가 폭발한다. 하지만 검은 블록은 꼭 필요한 칸에만 두면 되고, 블록을 없애는 것이 다른 블록을 방해하지 않는다. 그래서 “지금 없앨 수 있는 블록을 없애기”를 되풀이하면 된다.
3단계 · 핵심 아이디어
- 상자 크기: 블록은 칸이 4개이고, 직사각형이 되려면 2개를 채워 6칸이 되어야 한다. 그러니 블록을 감싸는 상자가 2×3 또는 3×2(넓이 6)여야 한다. 상자가 3×3이나 1×4면 절대 안 된다.
- 채울 칸의 조건: 상자에서 블록이 아닌 두 칸이 모두 빈칸이고, 각 칸의 위쪽(같은 열의 0행까지)이 모두 비어 있어야 한다. 위에 무엇이 있으면 검은 블록이 떨어지다 걸린다.
- 되풀이: 조건을 만족하는 블록을 하나 없애고 처음부터 다시 본다. 블록을 없애면 그 아래 칸이 열려 다른 블록이 가능해질 수 있기 때문이다. 없앤 블록 수가 답이다.
- 없앨 수 있는 블록을 먼저 없애도 손해가 없다. 블록을 없애면 빈칸만 늘어, 다른 블록의 조건이 나빠지지 않는다.
4단계 · 코드 흐름
- 되풀이: 블록 번호별로 칸 목록을 모은다.
- 블록마다 상자(행·열의 최소·최대)를 구한다. 넓이가 6이 아니면 넘어간다.
- 상자에서 블록이 아닌 칸이 모두 비어 있고 위로 떨어뜨릴 수 있으면, 블록 칸을 0으로 바꾸고 개수를 1 늘린 뒤 1로 돌아간다.
- 한 바퀴 동안 없앤 블록이 없으면 개수를 돌려준다.
5단계 · 파이썬 코드
from collections import defaultdict
def solution(board):
N = len(board)
b = [row[:] for row in board]
def can_drop(r, c): # 위에서 (r, c)까지 떨어뜨릴 수 있나
return all(b[i][c] == 0 for i in range(r + 1))
removed = 0
while True:
cells = defaultdict(list)
for r in range(N):
for c in range(N):
if b[r][c]:
cells[b[r][c]].append((r, c))
done = False
for bid, cs in cells.items():
r1, r2 = min(r for r, _ in cs), max(r for r, _ in cs)
c1, c2 = min(c for _, c in cs), max(c for _, c in cs)
if (r2 - r1 + 1) * (c2 - c1 + 1) != 6:
continue
holes = [(r, c) for r in range(r1, r2 + 1) for c in range(c1, c2 + 1) if b[r][c] != bid]
if all(b[r][c] == 0 and can_drop(r, c) for r, c in holes):
for r, c in cs:
b[r][c] = 0
removed += 1
done = True
break # 판이 바뀌었으니 처음부터 다시
if not done:
return removed
b = [row[:] for row in board]: 보드를 복사해 원본을 바꾸지 않는다.all(b[i][c] == 0 for i in range(r + 1)): 0행부터 r행까지 그 열이 모두 비었는지 본다. r행 자신도 비어 있어야 한다.
6단계 · 실행 추적
문제의 예시(번호는 0부터 센 (행, 열))
| 바퀴 | 블록 | 상자 | 채울 칸 | 판정 |
|---|---|---|---|---|
| 1 | 1 | 8~9행, 0~2열 | (8, 1), (8, 2) | 블록 2가 차지 → 안 됨 |
| 1 | 2 | 7~8행, 1~3열 | (7, 1), (7, 2) | 비었고 위도 빔 → 없앰 |
| 2 | 1 | 8~9행, 0~2열 | (8, 1), (8, 2) | 이제 비었고 위도 빔 → 없앰 |
| 2 | 3 | 6~8행, 4~5열 | (6, 5), (7, 5) | (6, 5) 위에 블록 4 → 안 됨 |
| 2 | 4 | 4~6행, 5~6열 | (4, 5), (6, 5) | (6, 5) 위에 블록 4 자신 → 안 됨 |
| 2 | 5 | 7~9행, 8~9열 | (8, 8), (9, 8) | 위에 블록 5 자신 → 안 됨 |
셋째 바퀴에는 없앨 블록이 없다. 답은 2다.
7단계 · 복잡도와 흔한 실수
한 바퀴에 보드 N² 칸을 보고, 바퀴는 블록 수(≤ 200) + 1번 이하다. 50×50이면 약 50만 번이라 금방 끝난다.
- 채울 칸만 비었는지 보고, 그 위가 막혔는지를 보지 않는다.
- 블록을 하나 없앤 뒤 처음부터 다시 보지 않아, 뒤늦게 열린 블록을 놓친다.
- 상자 넓이가 6인지 먼저 거르지 않아, 가운데가 튀어나온 모양 등을 잘못 센다.