[프로그래머스] [1차] 프렌즈4블록 파이썬 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

 

 

1. 풀이

• 완전탐색이다

board 전체를 완전탐색해서 사라질 블록들을 찾아 제거하고, 다시 또 완전탐색해서 사라질 블록들을 찾아 제거하는 것을 반복한다. board는 한 번 탐색하고 블록을 제거하고나면 상태가 달라지기 때문에 다시 완전탐색을 해서 새로 사라질 블록을 찾아 제거해야 한다.

while True: # board 탐색을 반복할 while문

	# board를 탐색하기 위한 이중 for문
	for i in range(m - 1):
    	for j in range(n - 1):
        	board[i][j]

그러면 board를 탐색하기 위한 이중 for문과 해당 board 탐색을 반복할 while문이 해당 for을 감싼 형태로 코드가 구상된다.

 

 

• 삭제될 블록을 표시할 배열을 활용하자

블록이 삭제되는 조건은 board[i][j] == board[i][j + 1] == board[i + 1][j] == board[i + 1][j + 1]일 때이다. 즉, board를 완전탐색하면서 각 블록이 해당 조건을 만족한다면 (i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)이 삭제될 것이라고 표시해두어야 한다. 그 표시를 board와 동일한 크기의 2차원 배열 shell에다가 하자. 초기 값은 0이고, 삭제될 블록이라면 1로 초기화한다.

단, shell은 매번 초기화되어야 한다. 한 번 board를 탐색하고나서 블록이 삭제되면, 이제 새롭게 삭제될 블록을 찾아야 하기 때문이다.

 

 

• board의 열을 기준으로 쪼개서, 밑에서부터 블록을 삭제해 가자.

우선 블록은 좌우가 아닌, 아래로 이동하기 때문에 board를 열을 기준으로 쪼개서 생각하자. 보통 2차원 배열을 순회할 때 행(i)이 바깥 for문이고 열(j)이 안쪽 for문이지만, 이 경우엔 열(j)이 바깥 for문이고 행(i)이 안쪽 for문이다.

블록이 제거되면 그 위에 있는 블록들이 밀려 내려온다. 따라서 가장 마지막 행인 (m - 1)행부터 블록이 사라지는지 아닌지 확인해가며 0행으로 올라와야 한다. 만약 shell[i][j]가 1, 즉 삭제해야 하는 블록이라면 shell[x][j]가 0일 때까지 계속 i - 1, i - 2하면서 위의 행으로 올라가고, shell[x][j] == 0이면 board[i][j]에 board[x][j] 값을 넣어준다.

 

 

 

2. 정답 코드

def solution(m, n, board):
    answer = 0
    board = [list(b) for b in board]

    while True:
        shell = [[0] * n for _ in range(m)] # 1: 지워질 블록
        popped = pop_blocks(m, n, board, shell)

        if popped == 0:
            break

        answer += popped

        for j in range(n):
            for i in range(m - 1, 0, -1):
                if shell[i][j] == 0:
                    continue

                board[i][j] = "-"
                for x in range(i - 1, -1, -1):
                    if shell[x][j] == 0:
                        board[i][j] = board[x][j]
                        board[x][j] = "-"
                        shell[i][j] = 0
                        shell[x][j] = 1
                        break

    return answer


def pop_blocks(m, n, board, shell):
    result = set()
    for i in range(m - 1):
        for j in range(n - 1):
            if is_removable(board, i, j):
                shell[i][j] = 1
                shell[i][j + 1] = 1
                shell[i + 1][j] = 1
                shell[i + 1][j + 1] = 1
                result.update({(i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1)})
    return len(result)


def is_removable(board, i, j):
    return (
        board[i][j] != "-"
        and board[i][j] == board[i][j + 1] == board[i + 1][j] == board[i + 1][j + 1]
    )