[백준19235번] 모노미노도미노 / Python3

문제 링크

나의 풀이

우선 문제를 푸는 방법을 크게 정리하면 다음 과정을 거친다.

1. 주어지는 블럭을 내려보낸다.
2. 행(green) 또는 열(blue)가 꽉 찬 곳이 있는지 확인
   1. 있다면 해당 행 또는 열을 비워준다.
   2. 아래 빈 공간이 있는 블럭들을 아래로 내려보낸다.
   3. 2번의 과정을 반복한다.
3. 연한 색의 칸에 블럭이 존재하는지 확인
   1. 존재한다면 해당 개수만큼 pop -> append

• [주의해야할 점]

큰 흐름으로 보면 그다지 어려워보이지 않지만 까다로운 조건들이 몇가지 있었다. 첫번째로 가로로 된 블록의 경우 붙어있어야 된다는 것이다.

0 0 0 0                 0 0 0 0    
0 0 0 0                 0 0 0 0 
0 0 0 0       ->        0 0 0 0 
2 2 0 0       ->        2 2 0 0 
0 1 0 0                 0 0 0 0 
0 0 0 0                 0 1 0 0 

예를들어, 1이 한칸짜리 블럭이고 2가 가로로 연결된 블록이라면 왼쪽과 같은 상태에서 블럭을 내린다면 오른쪽과 같이 1의 오른쪽이 비어있어도 2의 오른쪽 블럭은 내려오지 않는다는 것이다.

두번째로 꽉 찬 행 또는 열이 여러개가 동시에 존재한다면 모두 없애고 블럭을 내려주어야한다는 것이다. 만약, 한 줄 삭제하고 내리는 순간 위에서도 존재하던 행이 흐트러지기 때문이다.

마지막으로 블록을 내릴때는 아래 행부터 행 단위로 내려주어야한다는 것이다. 필자가 이 부분 때문에 디버깅에 많은 시간을 투자했다...

0 0 0 0                 0 0 0 0    
0 0 0 0                 0 0 0 0 
0 0 0 0       ->        0 0 0 0 
2 2 0 0       ->        2 2 0 0 
0 1 0 0                 0 0 0 0 
0 0 0 0                 0 1 0 0 

열을 기준으로 가로블럭이 있을때 왼쪽 블럭을 기준으로 내리게 된다면 위의 상황과 같이 위에 2인 가로 블럭이 내려오지 않게 된다. 따라서 행을 기준으로 아래 행부터 내려갈 수 있는 블록을 내리는 방법으로 풀어내야했다.

• [green과 blue의 구분]

green은 세로로 blue는 가로로 되어있다. 필자는 green과 blue를 같은 크기(4*6)의 2차원 배열을 만들어 블럭을 관리했다. green의 경우 블럭이 주어지는 위치에서 y값을 기준으로 블럭을 내리되 t가 2인 블럭에 한해서 가로 블럭으로 처리를 해주었고 blue의 경우 블럭이 주어지는 위치에서 x값을 기준으로 블럭을 내리되 t가 3인 블럭에 한해서 가로 블럭으로 처리를 해주었다. 이렇게 해줌으로써 처음 블럭을 내릴때 빼고는 모두 같은 범위의 인덱스로 처리를 해줄수 있어 구현에 편리했다.

• [블럭 내리기]

처음 블럭을 내리는 것을 구현할 때 아래에서부터 0이 나올때까지 탐색을 한 뒤 0이 되는 시점의 인덱스에 블럭을 위치시켰다. 그러나 이렇게 하면 안된다.

0 0 0 0                 0 0 0 0    
0 0 0 0                 0 0 0 0 
0 0 0 0       ->        0 0 0 0 
2 2 0 0       ->        2 2 0 0 
1 0 0 0                 1 1 0 0 
1 1 0 0                 1 1 0 0 

위처럼 1인 블럭을 (0, 1)위치에서 내려보낸다면 2와 1사이의 공간으로 들어가 버리기때문이다. 따라서 필자는 위에서부터 0이 아닌 곳이 나올 때까지 탐색을 한 뒤 블럭을 위치시켰다.

• [연한 부분의 특수 칸 처리]

이 부분은 4번과 5번 행렬에 블럭이 있는지 체크하면서 개수를 체크한다. 여기서 개수는 0, 1, 2개가 될 수 있다. 이후 해당 개수만큼 앞쪽을 pop해주고 뒤에 [0, 0, 0, 0]을 append해주는 방식으로 구현하였다. 이렇게 말고 단순히 4번째 칸에 블럭이 존재한다면 pop(0) -> append([0] * 4)를 반복하는 방법으로도 구현이 가능하다.

코드

# 19235번 모노미노도미노
import sys


def print_green():
    for i in green[::-1]:
        print(*i)


def print_blue():
    for i in blue[::-1]:
        print(*(i[::-1]))


def down_block_green(t, x):
    global green

    if t in [1, 3]:
        i = 4
        while i > 0 and green[i-1][x] == 0:
            i -= 1
        green[i][x] = 1
        if t == 3:
            green[i+1][x] = 1
    elif t == 2:
        i = 4
        while i > 0 and green[i-1][x] == 0 and green[i-1][x+1] == 0:
            i -= 1
        green[i][x] = green[i][x+1] = 2


def down_block_blue(t, x):
    global blue

    if t in [1, 2]:
        i = 4
        while i > 0 and blue[i-1][x] == 0:
            i -= 1
        blue[i][x] = 1
        if t == 2:
            blue[i+1][x] = 1
    elif t == 3:
        i = 4
        while i > 0 and blue[i-1][x] == 0 and blue[i-1][x+1] == 0:
            i -= 1
        blue[i][x] = blue[i][x+1] = 2


def find_bang(board):
    global score

    is_exist = False
    for i in range(4):
        if board[i].count(0) == 0:
            score += 1
            board[i] = [0] * 4
            is_exist = True

    return is_exist


def down_with_bang(board):
    for j in range(1, 6):
        for i in range(4):
            if board[j][i] == 1 and board[j-1][i] == 0:
                k = j-1
                while k > 0 and board[k-1][i] == 0:
                    k -= 1
                board[k][i] = 1
                board[j][i] = 0
            elif i < 3 and board[j][i] == 2 and board[j][i+1] == 2:
                if board[j-1][i] == 0 and board[j-1][i+1] == 0:
                    k = j-1
                    while k > 0 and board[k-1][i] == 0 and board[k-1][i+1] == 0:
                        k -= 1
                    board[k][i] = board[k][i+1] = 2
                    board[j][i] = board[j][i+1] = 0


def find_light(board):
    cnt = 0
    for i in range(4, 6):
        if not board[i].count(0) == 4:
            cnt += 1

    for _ in range(cnt):
        board.pop(0)
        board.append([0] * 4)


def cnt_block():
    global green, blue

    cnt = 0
    for i in range(4):
        for j in range(4):
            if green[i][j] != 0:
                cnt += 1
            if blue[i][j] != 0:
                cnt += 1
    return cnt


# 메인 로직
green = [[0] * 4 for _ in range(6)]
blue = [[0] * 4 for _ in range(6)]
board = [green, blue]
score = 0

for _ in range(int(sys.stdin.readline())):
    t, x, y = map(int, sys.stdin.readline().split())

    # 처음 블럭 내려감
    down_block_green(t, y)
    down_block_blue(t, x)

    for color in board:
        while find_bang(color):     # 행 or 열이 터지는지 확인
            down_with_bang(color)   # 블럭 내리기
        find_light(color)           # 연한 블럭 내리기

print(score)
print(cnt_block())