📃 문제 설명

프렌즈4블록

[문제 출처 : 프로그래머스]

👨‍💻 해결 방법

나의 생각의 흐름을 주절주절..

4개가 붙어있는 경우 블록을 터뜨려야하므로,
보드를 돌면서 4개가 붙어있는 경우를 체크하여 좌표를 저장한다.
이 때, 중복을 방지하기 위해 set을 사용했다.

그리고 set에 저장된 좌표를 빈자리로 만들고 다시 보드를 도는 방식으로 반복하다가, 더 이상 터뜨릴 블록이 없을 때(set이 비어있을 때)종료하면 된다.

그런데 생각해봐야할 문제가, 두 가지 있었다.

첫 번째로, 중간에 있는 블록이 터질경우 윗 블록들이 아래로 떨어져야 하는데, 이것을 처리해야 한다.
보드가 2차원 리스트로 주어지기 때문에 아래로 떨어지는 것을 구현하기가 복잡했다. 그래서 보드를 우측으로 90도 회전시켰다. 그렇게 되면 한 행을 큐의 개념으로 pop시키면 우측 블록들이 자연스럽게 빈공간을 채우게 된다.

하지만 여기서 두 번째 문제가 생긴다. 한 행에서 터뜨려야 할 블록이 두 개 이상일 때, 미리 저장되어 있는 좌표들에 pop을 사용하면 pop되면서 인덱스가 꼬인다.

나는 이 문제를 해결하기 위해, 우선 터뜨려야 할 자리를 바로 pop하지 않고 0으로 채웠다.

그리고 다시 그 행에서 0이 아닌 값들로만 채운 배열을 만들고 그 뒤에 0의 갯수만큼 -1을 채워서 행을 완성한다. 이렇게 하면 가운데 블록들이 사라지고 빈자리를 우측블록이 채우게 된다.

이 때 -1은 빈자리를 의미하므로 터뜨려야할 블록을 체크할 때 -1은 예외처리 해주었다.

결론

보드를 우측으로 90도 회전하여, 블록이 터지면 위에서 아래로 블록이 체워지는게 아니라 우측에서 좌측으로 채워지도록 하여, 큐의 개념을 활용하여 구현했다.

보드를 돌면서 4개가 붙어있는 경우 좌표를 저장하고, 더 이상 터뜨릴 블록이 없을 때 까지 반복하며, 블록을 터트리고 빈자리를 -1로 채우는 과정을 반복한다.

블록이 터질 때 마다 횟수를 카운트하여 반환하면 끝

👨‍💻 소스 코드

def solution(m, n, board):
    answer = 0
    newBoard = []

    for i in range(n):
        temp = []
        for j in range(m - 1, -1, -1):
            temp.append(board[j][i])
        newBoard.append(temp)

    while True:
        boom = set()
        for i in range(1, n):
            for j in range(1, m):
                if newBoard[i - 1][j - 1] == newBoard[i - 1][j] == newBoard[i][j - 1] == newBoard[i][j] != -1:
                    boom |= {(i, j), (i - 1, j - 1), (i - 1, j), (i, j - 1)}
        if not boom:
            break
        for i, j in boom:
            newBoard[i][j] = 0
        for i in range(n):
            newBoard[i] = [item for item in newBoard[i] if item != 0]
            for k in range(m - len(newBoard[i])):
                newBoard[i].append(-1)
                answer += 1
    return answer