[221001] 백준 20061 : 모노미노도미노 2

https://www.acmicpc.net/problem/20061

20061번: 모노미노도미노 2

1. 연습장의 필요성

 위 문제는 종이 갖다 두고 정리하면서 풀어야 한다. 왜냐하면 모든 조건들이 조건항으로 제시되는 게 아니라 구구절절 설명을 해놓았기 때문이다. 하나씩 차근차근 정리해보자

 가) 각각의 보드판 정의하기

문제에서 보면 빨간판과 초록판, 그리고 파란판이 붙어있다. 빨간 판은 설명을 위해 만든 가상의 판이므로 굳이 여기서부터 구현할 필요가 없고, 초록판과 파란판만 보드로 만들어주면 된다. 그리고 블록이 이동할 때 좌표값만 신경 써주면 된다. 

 위의 그림과 같이 놓여져 있는 좌표점에서 초록판은 y값이 고정이고, 파란판은 x값이 고정이다. 따라서 각 판의 시작 포인트로 점을 옮겨서 활용하면 된다.

 나) 블록의 정의 방식 확인하기

 각 블록은 t(type) 과 시작 좌표가 주어진다.

t = 2, 3 일 때 초록판과 파란판에 따라서 조건문이 살짝 달라진다.

각각의 경우에 따라서 초록판은 t = 3일 때, X+1의 함수가 경계 밖을 넘지 않도록 해줘야 하고, 파란판의 경우에는 t = 2 일 때, Y+1 이 보드 경계 밖을 안 나가도록 해줘야 한다. 다음은 초록판에 대해서 블록들이 움직일 때 조건문들이다.

if 0 <= nx < 6 and 0 <= ny < 4 :
    if t == 1 :
        if green_board[nx][ny] == 0 :
            gq.append([t, nx, ny])
    if t == 2 :
        if green_board[nx][ny] == 0 and green_board[nx][ny + 1] == 0 :
            gq.append([t, nx, ny])
    if t == 3 and 0 <= nx + 1 < 6 :
        if green_board[nx][ny] == 0 and green_board[nx + 1][ny] == 0 :
            gq.append([t, nx, ny])

 다) 줄 없애기

 줄 없애는 문제를 해결하는 것이 제일 어려웠다. 파이썬 내장함수인 del과 insert를 써서 관리하려고 했는데, 줄이 여러 개인 경우에는 처리가 어려워진다. 그렇다고 Numpy를 쓸 수 없기 때문에 여러 줄 없애는 코드를 구현해야 했다. 그래서 한 가지 아이디어를 낸 것이 temp로 빈 보드판을 만들고 줄이 완성되어있는 곳은 생략하고 뒤에서부터 수를 입력해서 원래 있던 보드판에 갱신을 해주는 것이다. 또한, 이렇게 하면 줄이 완성된 경우와 연한 칸에 블록이 있는 경우가 동시에 발생했을 때 처리도 가능해진다. 초록판의 상황을 가정한 예시는 다음과 같다.

 라) 연한 칸에 있는 블록 여부에 따른 줄 없애기

 이건 생각보다 쉽다. 각 열 / 행에 블록이 존재하면 맨 아랫줄부터 지워주면 된다. 2개면 2개 지우고, 1개면 1개 지우면 된다. del 로 지워주고 insert로 앞부분에 0으로 초기화된 배열 또는 값을 넣어줌으로써 해결할 수 있다.

2. 전체 코드

메모리 : 125116 KB, 시간 : 568 ms, 풀이시간 : 180 min + a

※ 문제를 해결하긴 했지만 아이디어를 떠올리고 해결하는데 많은 시간이 소요되었다. 그래도 좋은 문제였던 것 같음. 다음에 다시 풀어봐야겠다.

※ 함수 이름

 move() :  이동하는 함수 

 delete() : 완성된 줄 없애는 함수

 pastel_delete(num_row, num_col) : 연한 곳에 블록이 있을 경우에 줄 제거하는 함수

N = int(input())
info_block_q = [list(map(int, input().split())) for _ in range(N)]

green_board = [[0 for _ in range(4)] for _ in range(6)]
blue_board = [[0 for _ in range(6)] for _ in range(4)]

# 하, 우
dx, dy = [1, 0], [0, 1]
# move
def move(t, x, y) :
    gq = [[t, 0, y]]
    bq = [[t, x, 0]]
    while gq :
        t, x, y = gq[0]
        del gq[0]
        nx = x + dx[0]
        ny = y + dy[0]
        if 0 <= nx < 6 and 0 <= ny < 4 :
            if t == 1 :
                if green_board[nx][ny] == 0 :
                    gq.append([t, nx, ny])
            if t == 2 :
                if green_board[nx][ny] == 0 and green_board[nx][ny + 1] == 0 :
                    gq.append([t, nx, ny])
            if t == 3 and 0 <= nx + 1 < 6 :
                if green_board[nx][ny] == 0 and green_board[nx + 1][ny] == 0 :
                    gq.append([t, nx, ny])
    gx, gy = x, y
    while bq :
        t, x, y = bq[0]
        del bq[0]
        nx = x + dx[1]
        ny = y + dy[1]
        if 0 <= nx < 4 and 0 <= ny < 6 :
            if t == 1 :
                if blue_board[nx][ny] == 0 :
                    bq.append([t, nx, ny])
            if t == 2 and 0 <= ny + 1 < 6 :
                if blue_board[nx][ny] == 0 and blue_board[nx][ny + 1] == 0 :
                    bq.append([t, nx, ny])
            if t == 3 :
                if blue_board[nx][ny] == 0 and blue_board[nx + 1][ny] == 0 :
                    bq.append([t, nx, ny])
    bx, by = x, y
    if t == 1 :
        green_board[gx][gy], blue_board[bx][by] = 1, 1
    if t == 2 :
        green_board[gx][gy], blue_board[bx][by] = 1, 1
        green_board[gx][gy+1], blue_board[bx][by+1] = 1, 1
    if t == 3 :
        green_board[gx][gy], blue_board[bx][by] = 1, 1
        green_board[gx + 1][gy], blue_board[bx + 1][by] = 1, 1

def delete():
    global score
    # 줄 어떻게 지우지
    temp = [[0 for _ in range(4)] for _ in range(6)]
    it = 5
    for i in range(5, -1, -1):
        if green_board[i].count(1) != 4:
            for j in range(4):
                temp[it][j] = green_board[i][j]
            it -= 1
        else : score += 1
    for i in range(6):
        for j in range(4):
            green_board[i][j] = temp[i][j]
    temp = [[0 for _ in range(6)] for _ in range(4)]
    cnt = 0
    it = 5
    for i in range(5, -1, -1):
        for j in range(4):
            if blue_board[j][i] == 1 : cnt += 1
        if cnt != 4 :
            for j in range(4):
                temp[j][it] = blue_board[j][i]
            it -= 1
        else : score += 1
        cnt = 0
    for i in range(4):
        for j in range(6):
            blue_board[i][j] = temp[i][j]

def pastel_delete(num_row, num_col) :
    if num_row != 0 : # green_board
        for i in range(4):
            green_board[-1][i] = 0
        del green_board[-1]
        green_board.insert(0, [0 for _ in range(4)])
        if num_row == 2 :
            for i in range(4):
                green_board[-1][i] = 0
            del green_board[-1]
            green_board.insert(0, [0 for _ in range(4)])
    if num_col != 0 : # blue_board
        for i in range(4):
            del blue_board[i][-1]
            blue_board[i].insert(0, 0)
        if num_col == 2 :
            for i in range(4):
                del blue_board[i][-1]
                blue_board[i].insert(0, 0)

def solve():
    while info_block_q :
        t, x, y = info_block_q[0]
        del info_block_q[0]
        move(t, x, y)
        delete()
        # Green Board count
        row, col = 0, 0
        for i in range(2):
            if green_board[i].count(1) > 0 :
                row += 1
            for j in range(4):
                if blue_board[j][i] != 0 :
                    col += 1
                    break
        pastel_delete(row, col)
    num_tile = 0
    for i in range(6):
        num_tile += green_board[i].count(1)
    for j in range(4):
        num_tile += blue_board[j].count(1)
    return num_tile

score = 0
result = solve()
print(score)
print(result)