글 작성자: 택시 운전사
반응형

🧱 프렌즈 4 블록 문제 풀어보기


😃 나의 코드

dx = [0, 1, 0, 1]
dy = [0, 0, 1, 1]

def safe(width, height, c_idx, r_idx):
    for x, y in zip(dx,dy):
        if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
            return False
    return True

def del_check(board, c_idx, r_idx):
    square_set = set()
    for x, y in zip(dx,dy):
        square_set.add(board[y+r_idx][x+c_idx])
    if len(square_set) == 1 and square_set != {" "}:
        return True
    return False

def del_block(board, c_idx, r_idx):
    for x, y in zip(dx,dy):
        board[y+r_idx][x+c_idx] = ""
    return board
    
def total_del_block(board):
    total = 0
    for row in board:
        for block in row:
            if block == ' ':
                total += 1
    return total

def drop_block(width, height, board):
    for x_idx in range(width):
        tmp_lst = []
        for y_idx in range(height):
            tmp_lst.append(board[y_idx][x_idx])
        col_str = "".join(tmp_lst)
        col_str = (height-len(col_str))*" " + col_str
        for y_idx in range(height):
            board[y_idx][x_idx] = col_str[y_idx]
    return board

def solution(height, width, board):
    board = [[block for block in row] for row in board]
    answer = 0
    while True:
        del_lst = []
        for r_idx in range(height):
            for c_idx in range(width):
                if safe(width, height, c_idx, r_idx):
                    if del_check(board, c_idx, r_idx):
                        del_lst.append([c_idx, r_idx])
        if len(del_lst) == 0:
            break
        for del_pos in del_lst:
            board = del_block(board, del_pos[0], del_pos[1])
        board = drop_block(width, height, board)
    return total_del_block(board)

이 문제를 푸는 과정은 다음과 같습니다.


  1. 같은 모양의 2 X 2 블록을 찾는다.
  2. 그 블록을 제거한다.
  3. 블록을 아래로 떨어뜨려 빈 공간을 채운다.
  4. 더 이상 지울 블록이 없을 때까지 시행을 반복한다.


이런 시행이 잘 정리되고 각 시행별로 코드가 긴 문제는 각각의 시행을 함수로 만들어서 진행하면 코드가 덜 복잡하게 짤 수 있습니다. 문제 풀이에 앞서 편의를 위해

board = [[block for block in row] for row in board]

를 통해 board를 2차원 배열로 바꿔줍니다.

	del_lst = []
    for r_idx in range(height):
        for c_idx in range(width):
            if safe(width, height, c_idx, r_idx):
                if del_check(board, c_idx, r_idx):
                    del_lst.append([c_idx, r_idx])

우선 같은 모양의 2 X 2 블록을 찾는 과정입니다. 여기서 미리 만들어둔 dxdy를 이용합니다. dxdy는 각각 xy에 더해서 블록을 검증하는 역할을 합니다.

def safe(width, height, c_idx, r_idx):
    for x, y in zip(dx,dy):
        if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
            return False
    return True

우선 통과할 것은 safe()함수입니다. dxdy를 더하는 과정에서 boardindex를 넘는 경우를 미리 방지해주는 역할을 합니다.

def del_check(board, c_idx, r_idx):
    square_set = set()
    for x, y in zip(dx,dy):
        square_set.add(board[y+r_idx][x+c_idx])
    if len(square_set) == 1 and square_set != {" "}:
        return True
    return False

다음은 2 X 2 블록이 지워질 수 있는 지를 검증하는 del_check()함수입니다. 각 블록을 set 자료형에 추가하여 모두 같은 모양이라면 set의 크기가 1이고, 그 모양이 빈 공간이 아닐 시 True를 그 외에는 False를 반환합니다. del_check()을 통해 검증된 c_idxr_idxdel_lst에 저장됩니다.

def del_block(board, c_idx, r_idx):
    for x, y in zip(dx,dy):
        board[y+r_idx][x+c_idx] = ""
    return board

del_lst의 원소를 이용하여 board의 블록을 제거해줍니다. 만약 del_lst의 크기가 0이라면 지울 블록이 없다는 뜻이기 때문에 무한 루프를 break해줍니다.

def drop_block(width, height, board):
    for x_idx in range(width):
        tmp_lst = []
        for y_idx in range(height):
            tmp_lst.append(board[y_idx][x_idx])
        col_str = "".join(tmp_lst)
        col_str = (height-len(col_str))*" " + col_str
        for y_idx in range(height):
            board[y_idx][x_idx] = col_str[y_idx]
    return board

블록을 떨어뜨려 빈 공간을 채우는 과정입니다. 여러 방법이 있겠지만 저는 문자열을 이용하였습니다. 왼쪽부터 세로 배열을 받아 tmp_lst에 저장합니다. 그 배열을 join을 이용하여 빈 공간을 없에줍니다. 문자열 길이를 다시 높이에 맞추기 위해 앞에 빈 칸을 적절히 추가합니다. 이를 바탕으로 다시 board를 업데이트해줍니다. 이 과정을 사라질 블록이 없을 때까지 반복합니다.

def total_del_block(board):
    total = 0
    for row in board:
        for block in row:
            if block == ' ':
                total += 1
    return total

결과값은 전체에서 사라진 블록의 갯수를 구하는 것이기 때문에 board를 확인하면서 빈 칸인 블록의 갯수를 세면 문제는 마무리됩니다.

Written with StackEdit.


반응형