Programmers. 프렌즈4블록

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 프렌즈4블록

문제 풀이

블록을 깨고 나머지를 아래로 내려보낸다면 행처리에 상당히 애를 먹겠으나 행과 열을 바꾸면 처리가 쉽다는 것을 망각해버렸다. 행과 열을 바꾼 2차월 배열을 생성하고 전체 면적에 4칸을 순회탐색하여 깰 블록이 있는지 set에 넣고 있다면 터뜨리고 나머지 블록을 몰아넣는 과정을 반복하여 더 이상 전체 순회해도 터뜨릴 블록이 없을 때까지 수행한다.

• 행과 열을 서로 바꾼 2차원 배열을 선언한다.
• 전체 보드에서 4칸으로 탐색가능한 전체 범위를 탐색, 4칸이 빈 블록이 아니고 서로 값이 같다면 터뜨릴 블록의 좌표를 set에 입력
• 순회가 끝나고 터뜨릴 좌표가 담긴 set의 원소를 전부 터진 상태로 바꾸며 개수를 센다.
• 각 행에 대해 터진 원소의 수를 count하여 그만큼 빈 블록을 생성하고 그 뒤에 터지지 않은 블록을 압축한 배열을 붙이고 다시 탐색한다.
• 더 이상 터지는 블록이 없을 때까지 탐색

python 코드

def solution(m, n, board):
    def check(i, j):
        a = grid[i][j]
        b = grid[i + 1][j]
        c = grid[i][j + 1]
        d = grid[i + 1][j + 1]
        if a == b == c == d != "_":
            pop_set.add((i, j))
            pop_set.add((i + 1, j))
            pop_set.add((i, j + 1))
            pop_set.add((i + 1, j + 1))
            return True
    grid = []
    for i in range(len(board[0])):
        buf = []
        for j in range(len(board)):
            buf.append(board[j][i])
        grid.append(buf)
    answer = 0
    while True:
        pop_set = set()
        for r in range(len(grid) - 1):
            for c in range(len(grid[0]) - 1):
                check(r, c)
        if len(pop_set) == 0:
            break
        answer += len(pop_set)
        for i, j in list(pop_set):
            grid[i][j] = "X"
        for i, g in enumerate(grid):
            grid[i] = ["_"] * g.count("X") + [b for b in g if b != "X"]
    return answer