(BOJ20061 모노미노도미노 2

• tags : (algorithm

  No matching post could be found

  - (simulate
• 문제 링크 : https://www.acmicpc.net/problem/20061
• 풀이 링크
  • Python

• 주어진 입력에 따라 구현하면 되는 문제
• 주어진 구조가 조금 독특하여 해당 구조를 탐색, 적용하는 것이 조금 번거로울 수 있다.
• 우선 블록이 주어지면, 두 방향으로 최대한 이동한 후, 테트리스 처럼 맞추어진 줄을 제거, 해당 방향으로 윗 블럭들을 당긴다.
• 그리고 특정 구간에 블록이 없도록 이동시켜주는 작업도 필요하다.

if __name__ == "__main__":
    board = [[0] * 10 for _ in range(10)]
    points = 0
    for _ in range(int(input())):
        t, x, y = map(int, input().split())
        if t == 1:
            blocks = ((x, y),)
        elif t == 2:
            blocks = ((x, y), (x, y + 1))
        elif t == 3:
            blocks = ((x, y), (x + 1, y))
        points += move_blocks(blocks)
    print(points)
    print(count_blocks())

• 우선 기본적인 풀이코드 구조는 다음과 같다.
• 게임 보드는 “ㄱ”모양 이지만, 해당 모양으로 자료구조를 선언하는것이 불편하기 때문에 10 * 10 크기로 선언했다.
• 게임을 진행하며 얻을 점수를 저장할 points 변수도 선언했다.
• 순서대로 입력 받으며 문제를 해결하는데, 기본적으로move_blocks()함수를 호출하여 해결한다.

def move_blocks(blocks: Block) -> int:
    global board
    points = 0
    green_pos = move_single_block(blocks, True)
    blue_pos = move_single_block(blocks, False)
    points += push_blocks(green_pos, True)
    points += push_blocks(blue_pos, False)
    return points

• 각 순서를 진행하는 move_blocks()함수
• 여기서 move_single_block()함수와 push_blocks()함수를 호출하여 해결한다
  • move_single_block()함수는 처음 생성된 블록을 초록, 파랑 영역으로 보내는 함수이고,
  • push_blocks()함수는 각 줄이 완성되어 점수를 낼 수 있는지, 비어 있는 줄 또는 존재할 수 없는 곳에 블록이 있는 경우 이동시켜주는 함수이다.

def move_single_block(blocks: Block, is_green: bool) -> Block:
    def check_board(blocks: Block, is_green: bool) -> bool:
        for x, y in blocks:
            if is_green and x >= 10:
                return False
            elif not is_green and y >= 10:
                return False
        return True

    while True:
        if is_green:
            next_blocks = tuple((x + 1, y) for x, y in blocks)
        else:
            next_blocks = tuple((x, y + 1) for x, y in blocks)
        if not check_board(next_blocks, is_green):
            return blocks
        if not check_blocks(next_blocks):
            return blocks
        blocks = next_blocks


def check_blocks(blocks: Block) -> bool:
    global board
    for x, y in blocks:
        if board[x][y]:
            return False
    return True

• 각 블록을 이동시키는 함수들이다.
• 우선 move_single_block()이 호출되면, 블록을 이동하며 해당 위치에 블록을 둘 수 있는지 확인한다.
  • 이 과정은 다시 두가지로 나뉘는데,
  • 첫 번째는 10 * 10 공간을 벗어나지 않는지 확인하고,
  • 다른 블록과 겹치지 않는지 확인한다.

def push_blocks(blocks: Block, is_green: bool) -> int:
    global board
    points = 0
    for x, y in blocks:
        board[x][y] = 1
    for i in range(6, 10):
        if check_line(i, is_green):
            points += 1
            pull_lines(i, is_green)
    for i in range(4, 6):
        for j in range(4):
            if is_green:
                if board[i][j]:
                    pull_lines(9, True)
                    break
            else:
                if board[j][i]:
                    pull_lines(9, False)
                    break
    return points


def check_line(line_idx: int, is_green: bool) -> bool:
    global board
    for j in range(4):
        if is_green:
            if board[line_idx][j]:
                continue
            return False
        else:
            if board[j][line_idx]:
                continue
            return False
    for j in range(4):
        if is_green:
            board[line_idx][j] = 0
        else:
            board[j][line_idx] = 0
    return True


def pull_lines(line_idx: int, is_green: bool) -> None:
    global board
    for i in range(line_idx - 1, 2, -1):
        for j in range(4):
            if is_green:
                board[i + 1][j] = board[i][j]
            else:
                board[j][i + 1] = board[j][i]

• 블록을 이동하는 것도 크게 두가지로 구분되어 동작한다.
• 먼저 각 줄마다 점수를 획득할 수 있는지, 그렇다면 해당 줄의 블록들을 제거한다.
• 그 다음으로 블록이 있으면 안되는 공간에 있다면, 해당 블록을 원하는 구역으로 넣을 대 까지 이동시켜준다.