문제 보기 · Level 2 · 2018 KAKAO BLIND RECRUITMENT (1차) · 정답률 59% · 푼 사람 15,189명 (2026-09-30 기준)1

문제

m×n 판에 블록이 대문자로 놓여 있다. 같은 블록 네 개가 2×2로 붙어 있으면 지운다. 그런 2×2가 여러 개면 겹치더라도 한꺼번에 지운다. 지운 뒤 위 블록이 아래로 떨어지고, 다시 지울 수 있으면 되풀이한다. 지워진 블록의 총수를 돌려준다.

  • 2 ≤ m, n ≤ 30

풀이

막히면 한 단계씩 펼친다.

필요한 개념

구현과 시뮬레이션: “찾기 → 한꺼번에 지우기 → 떨어뜨리기”를 더 지울 게 없을 때까지 되풀이한다. 한꺼번에 바뀌는 규칙은 표시해 두었다가 나중에 바꾼다.

1단계 · 작은 예로 손으로 풀기 
A A B
A A B
C C B
  1. 2×2를 모두 본다. 왼쪽 위 (A A / A A)만 같다 → 4칸 지움
  2. 지운 칸을 빈칸(.)으로: 
    . . B
. . B
C C B
  3. 떨어뜨린다: 왼쪽 두 열은 C가 이미 바닥에 있어 그대로다
  4. 다시 2×2를 보면 같은 것이 없다 → 끝

답은 4다. 두 2×2가 한 칸을 함께 쓰면(겹치면) 그 칸은 한 번만 센다. 예를 들어 A가 2×3으로 붙어 있으면 2×2가 두 개지만 지워지는 블록은 6개다. 겹친 2칸을 한 번 빼는 포함-배제 원리의 셈 4 + 4 − 2 = 6과 같다.

2단계 · 가장 단순한 방법과 그 속도

한 판을 볼 때 2×2는 최대 29 × 29 = 841개다. 판을 한 번 볼 때마다 적어도 4개가 지워지니 되풀이는 많아야 900 ÷ 4 = 225번이다. 모두 20만 번 정도라 넉넉하다. 이 문제는 규칙을 정확히 옮기는 문제다.

3단계 · 핵심 아이디어
  • 한꺼번에 지우기: 2×2를 찾는 동안에는 판을 고치지 않는다. 지울 칸의 좌표를 집합에 모은다. 집합이라 겹친 칸도 한 번만 들어간다. 다 찾은 뒤 한 번에 지운다.
  • 떨어뜨리기: 열마다 빈칸이 아닌 블록만 위에서 아래 순서로 모은다. 그 열을 모두 비우고, 모은 블록을 바닥부터 다시 쌓는다.
  • 끝내기: 지울 칸이 하나도 없으면 멈추고 지금까지 센 수를 돌려준다.
4단계 · 코드 흐름
  1. 문자열 줄들을 고칠 수 있게 글자 리스트의 리스트로 바꾼다.
  2. 되풀이:
    • 모든 2×2의 왼쪽 위 (r, c)마다 네 칸이 같고 빈칸이 아니면 네 좌표를 집합에 넣는다.
    • 집합이 비었으면 합계를 돌려준다.
    • 합계에 집합 크기를 더하고, 그 칸들을 빈칸으로 만든다.
    • 열마다 블록을 바닥으로 떨어뜨린다.
5단계 · 파이썬 코드 
def solution(m, n, board):
    b = [list(row) for row in board]            # 고칠 수 있는 2차원 리스트
    total = 0
    while True:
        hit = set()
        for r in range(m - 1):
            for c in range(n - 1):
                x = b[r][c]
                if x != "." and x == b[r][c + 1] == b[r + 1][c] == b[r + 1][c + 1]:
                    hit |= {(r, c), (r, c + 1), (r + 1, c), (r + 1, c + 1)}
        if not hit:
            return total
        total += len(hit)
        for r, c in hit:
            b[r][c] = "."
        for c in range(n):                      # 열마다 떨어뜨리기
            blocks = [b[r][c] for r in range(m) if b[r][c] != "."]   # 위→아래 순서
            for r in range(m):
                b[r][c] = "."
            for i, x in enumerate(reversed(blocks)):                  # 바닥부터 쌓기
                b[m - 1 - i][c] = x
  • list(row): 문자열 "CCBDE"를 ['C', 'C', 'B', 'D', 'E']로 바꾼다. 문자열은 칸을 고칠 수 없기 때문이다.
  • x == a == b == c: 네 값이 모두 같은지 한 줄로 비교한다.
  • hit |= {…}: 집합에 네 좌표를 더한다(합집합).
  • reversed(blocks): 맨 아래 블록부터 꺼내 바닥(m - 1)부터 채운다.
6단계 · 실행 추적

m = 4, n = 5, board = [“CCBDE”, “AAADE”, “AAABF”, “CCBBF”]

되풀이 찾은 2×2 지운 수 합계
1 A 2×3 덩어리 안의 2×2 두 개(겹침) 6 6
2 떨어진 뒤 생긴 2×2 8 14
3 없음   14

답은 14다. 되풀이 1에서 A 여섯 칸은 2×2 두 개가 가운데 두 칸을 함께 쓰지만 한 번씩만 셌다.

7단계 · 복잡도와 흔한 실수

되풀이 R번마다 판 전체(m·n)를 보니 \(O(R \cdot mn)\)이고, R ≤ mn / 4다.

  • 찾으면서 바로 지워서, 같은 차례에 지워져야 할 다른 2×2를 놓친다.
  • 겹친 칸을 두 번 센다.
  • 빈칸끼리 2×2가 같다고 보고 지운다(빈칸 검사 x != ".").
  • 위아래를 거꾸로 떨어뜨린다.
검증: 문제의 예시 2개를 통과했고, 6단계 표의 되풀이별 지운 수(6, 8)를 코드로 확인했다. 무작위 판 2,000개에서 “열을 문자열로 보고 빈칸을 지운 뒤 위를 채우는” 다른 풀이와 결과가 같았다 — 08_pg17679_p1.py

  1. 프로그래머스 스쿨, “[1차] 프렌즈4블록” (https://school.programmers.co.kr/learn/courses/30/lessons/17679), 2026-09-30 조회. ↩