[카카오 코테 2018 | python] [1차] 프렌즈4블록

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/17679
• Level2

 

Q1) 문제를 어떻게 이해했나요?
A1) 주어진 m x n 크기의 보드에서, 같은 캐릭터 4개가 2x2로 붙어 있으면 지워지고 그 위의 블록들이 아래로 떨어진다. 이 과정을 더 이상 지워질 블록이 없을 때까지 반복, 최종적으로 지워진 블록의 총 개수를 반환

Q2) 문제를 어떻게 풀 예정인가요?
A2) 
1. 보드를 2차원 배열로 변환
2. 2x2 블록 탐색하여 지워질 위치 기록
3. 지울 위치가 없으면 반복 종료
4. 지울 위치를 "0" 으로 표시하고 지움 처리
5. 아래에서부터 블록을 채워 넣음(중력 구현)
6. 반복하며 지워진 총 블록 개수 누적

 

✅ 최적의 코드

def solution(m, n, board):
    # 1. 문자열 배열을 리스트의 리스트로 변환
    board = [list(row) for row in board]
    total_removed = 0

    while True:
        # 2. 지워질 위치 찾기
        to_remove = set()
        for i in range(m - 1):
            for j in range(n - 1):
                block = board[i][j]
                if block == "0":
                    continue
                if block == board[i+1][j] == board[i][j+1] == board[i+1][j+1]:
                    to_remove |= {(i, j), (i+1, j), (i, j+1), (i+1, j+1)}

        # 3. 더 이상 지울 게 없으면 종료
        if not to_remove:
            break

        # 4. 블록 지우기
        for i, j in to_remove:
            board[i][j] = "0"
        total_removed += len(to_remove)

        # 5. 블록 떨어뜨리기
        for j in range(n):  # 열 단위
            empty = []
            for i in range(m-1, -1, -1):  # 아래에서 위로
                if board[i][j] == "0":
                    empty.append(i)
                elif empty:
                    empty_i = empty.pop(0)
                    board[empty_i][j], board[i][j] = board[i][j], "0"
                    empty.append(i)

    return total_removed