[프로그래머스] # 프렌즈4블록 (파이썬/Python)

📖 문제

[프로그래머스] # 프렌즈4블록 (파이썬/Python)

• 난이도: Level 3 같은 Level 2
• 유형: 구현

문제 요약

같은 문자가 2×2 형태로 붙어 있으면 해당 블록들을 모두 지우고, 위에 있는 블록이 아래로 떨어지는 게임이다.

이 과정을 반복하면서 최종적으로 지워진 블록의 총 개수를 구하는 문제이다.

---

🔍 문제 접근

💡 문제 분석

꼭 해야 하는 부분을 정리하면 다음과 같다

1. 2×2 탐색: 모든 칸에 대해 2×2 범위의 블록이 같은지 확인한다.
2. 2x2 삭제 처리: 한 번에 지워질 블록들을 표시한 뒤 삭제한다.
3. 중력 처리: 삭제된 칸 위에 있는 블록들을 아래로 떨어뜨린다.
4. 반복: 지울 블록이 더 이상 없을 때까지 위 과정을 반복한다.

 

🧠 풀이 아이디어

1. 문자열로 된 입력을 2차원 리스트로 바꾼다.
2. 각 라운드마다 다음을 반복한다:
   1. 2×2 블록 중 같은 문자로 이루어진 영역을 찾아 삭제 후보로 표시한다.
   2. 표시된 블록을 모두 지우고 개수를 센다.
   3. 중력을 적용해 위 블록을 아래로 내린다.
3. 삭제된 총 블록 수를 반환한다.

---

🔍 문제 풀이

🚩 제출한 소스 코드

def solution(m, n, board):
    # 1) board를 2차원 리스트로 변환
    grid = [list(row) for row in board]
    total_removed = 0

    while True:
        # 지워야 하는 칸 표시
        mark = [[False] * n for _ in range(m)]
        for i in range(m-1):
            for j in range(n-1):
                current = grid[i][j]
                if current and grid[i][j+1] == current \
                    and grid[i+1][j] == current \
                    and grid[i+1][j+1] == current:
                    mark[i][j] = mark[i+1][j] = mark[i][j+1] = mark[i+1][j+1] = True
        
        # True로 표시된 블록을 삭제 & 개수 세기
        removed_this_round = 0
        for i in range(m):
            for j in range(n):
                if mark[i][j]:
                    grid[i][j] = ""
                    removed_this_round += 1
        
        # 더이상 지울 블록이 없다면 반복 종료
        if removed_this_round == 0:
            break
            
        total_removed += removed_this_round
        
        # 중력 적용 -> 각 열마다 빈칸을 아래로 내리기 (어떻게 해야 하지?)
        # 빈 칸을 위로 올리고 블록은 아래로 쌓는다.
        # 즉, 빈칸 없애고 블록을 아래부터 순서대로 채워야 한다.
        for j in range(n):
            stack = []
            for i in range(m):
                if grid[i][j] != "":
                    stack.append(grid[i][j])
            
            for i in range(m-1, -1, -1):
                if stack:
                    grid[i][j] = stack.pop()
                        
                else:
                    grid[i][j] = ""  
    return total_removed

함수화해서 개선한 코드

def check_remove(m, n, grid):
    """
    2×2 같은 블록을 찾아서, 지울 칸을 True로 표시한 2D 배열을 반환한다.
    """
    mark = [[False] * n for _ in range(m)]
    for i in range(m-1):
        for j in range(n-1):
            current = grid[i][j]
            if current and grid[i][j+1] == current \
                and grid[i+1][j] == current \
                and grid[i+1][j+1] == current:
                mark[i][j] = mark[i][j+1] = mark[i+1][j] = mark[i+1][j+1] = True
    return mark

def remove_blocks(m, n, grid, mark):
    """
    mark 배열이 True인 칸으르 찾아서 빈칸으로 바꾸고,
    삭제된 블록의 총 개수를 반환한다.
    """
    removed = 0
    for i in range(m):
        for j in range(n):
            if mark[i][j]:
                grid[i][j] = ""
                removed += 1
    return removed

def down_blocks(m, n, grid):
    """
    중력을 적용하여, 각 열마다 빈칸 위의 블록을 아래로 당긴다.
    """
    for j in range(n):
        stack = []
        for i in range(m):
            if grid[i][j] != "":
                stack.append(grid[i][j])

        for i in range(m-1, -1, -1):
            if stack:
                grid[i][j] = stack.pop()

            else:
                grid[i][j] = ""  

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

    while True:
        # 2. 지울 칸 표시
        mark = check_remove(m, n, grid)
        # 3. 표시된 칸 삭제 및 개수 세기
        removed = remove_blocks(m, n, grid, mark)
        if removed == 0:
            # 더이상 지울 블록이 없다면 반복 종료
            break
        # 4. 전체 삭제 개수에 해당 칸의 삭제 개수 누적해서 더하기
        total_removed += removed
        # 5. 중력 적용
        down_blocks(m, n, grid)

    return total_removed

 

♻️ 전체 흐름

• `check_remove`: 지워질 블록들을 찾아 표시한다.
• r`emove_blocks`: 표시된 블록을 삭제하고, 삭제 개수를 반환한다.
• `down_blocks`: 삭제된 빈 칸 위에 있는 블록들을 아래로 떨어뜨린다.
• 위 세 과정을 반복하면서 총 삭제 블록 수를 누적한다.

 

🔍 check_remove(m, n, grid)

2×2 블록 중 같은 문자가 네 칸 모두 일치하면 mark 배열에 해당 위치를 True로 표시한다 mark 배열을 반환한다.

def check_remove(m, n, grid):
    """
    2×2 같은 블록을 찾아서, 지울 칸을 True로 표시한 2D 배열을 반환한다.
    """
    mark = [[False] * n for _ in range(m)]
    for i in range(m-1):
        for j in range(n-1):
            current = grid[i][j]
            if current and grid[i][j+1] == current \
                and grid[i+1][j] == current \
                and grid[i+1][j+1] == current:
                mark[i][j] = mark[i][j+1] = mark[i+1][j] = mark[i+1][j+1] = True
    return mark

• `mark`라는 크기 `m x n`의 2차원 리스트를 만들어 모두 `False`로 초기화한다.
• 이중 반복문으로 `(i, j)`를 좌측 상단으로 하는 2×2 블록을 전체 탐색한다.
  • `i`는 `0`부터 `m-2`까지, `j`는 `0`부터 `n-2`까지 순회한다.
• 현재 블록 문자(`grid[i][j]`)가 빈칸("")이 아니고,
  • 해당 네 칸을 `mark[i][j]`, `mark[i][j+1]`, `mark[i+1][j]`, `mark[i+1][j+1]`에 `True`로 표시한다.
• 그 아래(`i+1, j`), 오른쪽(`i, j+1`), 대각선(`i+1, j+1`) 위치도 모두 동일한 문자이면:
• 최종적으로 `mark` 배열을 반환한다.

 

🧹 remove_blocks(m, n, grid, mark)

mark 배열이 True인 칸을 찾아서 빈칸(””)으로 바꾸고, 삭제된 블록의 총 개수를 반환한다.

def remove_blocks(m, n, grid, mark):
    """
    mark 배열이 True인 칸으르 찾아서 빈칸으로 바꾸고,
    삭제된 블록의 총 개수를 반환한다.
    """
    removed = 0
    for i in range(m):
        for j in range(n):
            if mark[i][j]:
                grid[i][j] = ""
                removed += 1
    return removed

• `removed = 0`으로 초기화하여 삭제 개수를 센다.
• 이중 반복문으로 모든 칸(`i, j`)을 순회하며:
  • `mark[i][j]`가 `True`이면:
    • `grid[i][j] = ""`로 설정하여 해당 블록을 삭제한다.
    • `removed += 1`로 삭제 개수를 누적한다.
• 모든 블록 삭제 후 `removed`를 반환한다.

 

⬇️ down_blocks(m, n, grid)

중력을 적용하여, 각 열마다 빈칸 위의 블록을 아래로 당긴다.

def down_blocks(m, n, grid):
    """
    중력을 적용하여, 각 열마다 빈칸 위의 블록을 아래로 당긴다.
    """
    for j in range(n):
        stack = []
        for i in range(m):
            if grid[i][j] != "":
                stack.append(grid[i][j])

        for i in range(m-1, -1, -1):
            if stack:
                grid[i][j] = stack.pop()

            else:
                grid[i][j] = ""

• `j`를 `0`부터 `n-1`까지 순회하며 열 단위로 처리한다.
• 각 열마다 다음 작업을 수행한다:
  • `stack = []`를 생성해 현재 열에서 삭제되지 않은 블록 문자를 위에서부터 아래로 저장한다.
    • `i = 0`~ `m-1`까지 순회하며 `grid[i][j] != ""`이면 `stack.append(grid[i][j])`
  • 다시 아래에서 위로(`i = m-1 ~ 0`) 순회하면서:
    • `stack`이 비어있지 않으면 `stack.pop()`한 블록을 `grid[i][j]`에 채워 넣는다.
    • `stack`이 비어있으면 `grid[i][j] = ""`으로 빈칸 처리한다.

 

---

💡회고

• 중력 부분을 처리하는 것이 가장어려웠다. 해당 부분을 gpt를 통해서 힌트를 얻어서 풀이했다. 행-열 순서가 아니라 열-행 순서로 접근하는 것이 독특했다고 느꼈다. 이렇게 열 주심으로 접근해야 한다는 힌트를 얻을 수 있었다.
• 자바로도 풀이해볼 수 있으면 좋을 것 같다.