백준 알고리즘 19235번 모노미도미노 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/19235

19235번: 모노미노도미노

2020년도 상반기 삼성 SW 역량테스트를 변형한 문제라고 알고 있습니다. 다음 20년도 하반기를 준비하는 마음으로 풀어보았습니다.  이 문제의 핵심은 블록을 부수고, 부수었을 때 블록을 떨어뜨려야 하는데, 블록의 종류는 총 3가지가 있습니다. 이 중에서 가장 신경 써야 할 부분은 바로 2번 블록입니다. 

왼쪽부터 순서대로 블럭 1, 2 ,3 입니다.

블록 2번을 떨어뜨릴 때, 왼쪽 블록과 오른쪽 블록 모두 떨어질 수 있는 최대 깊이까지만 떨어뜨려야 합니다. 

예를 들어 블럭이 아래와 같은 상황이라고 가정하겠습니다.

위 그림과 같은 상태라고 하였을 때, 1번 블록은 가장 밑바닥층까지 떨어질 수 있지만, 2번 블록은 아래에 검은색 블록이 있으므로 떨어질 수 없습니다. 따라서 전체 블록은 떨어뜨리지 않아야 합니다. 이 경우를 처음에 간과하여 문제를 해결하는데 오랜 시간이 걸렸습니다. 저는 이 문제를 해결하기 위해 블록을 떨어뜨릴 때마다 같은 번호를 새겨서 체크하도록 하였습니다. 해결한 코드는 아래와 같습니다.

# sys모듈을 불러옵니다.
import sys
# 블럭 놓은 횟수를 입력받습니다.
n = int(sys.stdin.readline())
# 점수를 체크할 전역변수 score를 선언합니다.
score = 0
# 녹색 보드판과 파란색 보드판을 선언합니다.
greenboard = [[0] * 4 for _ in range(6)]
blueboard = [[0] * 4 for _ in range(6)]

# 각 열(y)마다 얼만큼 낮은 칸까지 떨어질 수 있는지 체크하는 서브함수입니다.
def dropblock(ny, board):
    nx = -1
    while 1:
        nx += 1
        if nx == 6:
            nx -= 1
            break
        elif board[nx][ny]:
            nx -= 1
            break
    return nx

# nx,ny에 있는 블럭이 최대 얼마나 낮게 떨어질 수 있는지 높이를 반환하는 서브함수입니다.
def dropblock2(ny, nx, board):
    while 1:
        nx += 1
        if nx == 6:
            nx -= 1
            break
        elif board[nx][ny]:
            nx -= 1
            break
    return nx

# 한줄이 꽉 찼을 때 블록을 떨어뜨리는 서브함수입니다.
def down(board):
    visit = {}
    for h in range(4, -1, -1):
        for w in range(4):
            if visit.get((h, w)) is None and board[h][w]:
                if w < 3 and board[h][w] == board[h][w + 1]:
                    min1 = dropblock2(w, h, board)
                    min2 = dropblock2(w+1, h, board)
                    min3 = min(min1, min2)
                    if min3 != h:
                        board[min3][w] = board[h][w]
                        board[min3][w + 1] = board[h][w + 1]
                        board[h][w] = 0
                        board[h][w + 1] = 0
                    visit[(h, w)] = 1
                    visit[(h, w + 1)] = 1
                else:
                    visit[(h, w)] = 1
                    idx = dropblock2(w, h, board)
                    if idx != h:
                        board[idx][w] = board[h][w]
                        board[h][w] = 0

# 보드의 점수를 체크하여 한줄이 꽉차면 점수를 채우고 블록을 떨어뜨리는 서브함수입니다.
def scorecheck(board):
    global score
    flag = 0
    for row in range(5, 1, -1):
        count = 0
        for w in range(4):
            if board[row][w]:
                count += 1
        if count == 4:
            score += 1
            for w in range(4):
                board[row][w] = 0
            flag = 1
    if flag:
        down(board)
        scorecheck(board)

# 가장 상단의 보드 2줄에 블록이 있을 경우, 하단의 블록들을 없애고 블록전체를 떨어뜨리는 서브함수입니다.
def cleanboard(board):
    count = 0
    for h in range(2):
        if sum(board[h]) > 0:
            count += 1
    for _ in range(count):
        for j in range(4):
            for i in range(5, 0, -1):
                board[i][j] = board[i - 1][j]
            board[0][j] = 0

# 메인함수입니다. 매 블록을 떨어뜨릴 때마다 위의 서브함수들을 사용하여 블록들을 천천히 쌓아올립니다.
for time in range(1, n + 1):
    t, x, y = map(int, sys.stdin.readline().split())
    if t == 1:
        ng = dropblock(y, greenboard)
        greenboard[ng][y] = time
        nb = dropblock(x, blueboard)
        blueboard[nb][x] = time
    elif t == 2:
        ng1 = dropblock(y, greenboard)
        ng2 = dropblock(y + 1, greenboard)
        ng = min(ng1, ng2)
        greenboard[ng][y] = time
        greenboard[ng][y + 1] = time
        nb = dropblock(x, blueboard)
        blueboard[nb][x] = time
        nb = dropblock(x, blueboard)
        blueboard[nb][x] = time
    else:
        nb1 = dropblock(x, blueboard)
        nb2 = dropblock(x + 1, blueboard)
        nb = min(nb1, nb2)
        blueboard[nb][x] = time
        blueboard[nb][x + 1] = time
        ng = dropblock(y, greenboard)
        greenboard[ng][y] = time
        ng = dropblock(y, greenboard)
        greenboard[ng][y] = time

    scorecheck(greenboard)
    scorecheck(blueboard)
    cleanboard(greenboard)
    cleanboard(blueboard)
# 각 보드판마다 블록 개수를 카운트할 변수 b,g를 선언합니다.
b = 0
g = 0
for i in range(6):
    for j in range(4):
        if greenboard[i][j]:
            g += 1
        if blueboard[i][j]:
            b += 1
# 최종 점수와 초록색 보드판의 블록 개수와 파란색 보드판의 블록 개수를 출력합니다. 
print(score)
print(b + g)

운이 좋게도 아직까지 Python으로 해결한 분들 중에는 시간이 가장 적게 걸려 1등을 기록하였습니다.

많은 분들이 도움을 받으셨으면 좋겠습니다. 소스코드에 대한 질문이 있으시다면 댓글남겨주시면 답변해드리겠습니다.