[프로그래머스] 블록 게임 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42894

코딩테스트 연습 - 블록 게임

 

빡구현 문제였다.

 

구현한 기능이 많다보니 100줄이 넘어갔다.

 

처음부터 봐보자.

 

일단 사용가능한 블록이 12가지가 있다.

하지만 게임 규칙대로라면 지울수 있는 블록은 5개로 줄여진다.

빨간 동그라미친 블록만 가능하다.

나머지 블록은 공백 위에 다른 1x1블록이 막고 있어서 꽉찬 블록을 만들 수 없기 때문이다.

따라서 5개의 블록만 사용이 가능하다.

 

나는 5개 모양 블록을 그냥 배열로 만들었다.

 

일단 알고리즘 순서는 다음과 같다.

1. 각 블록을 포함하는 가장작은 사각형의 가장왼쪽,위 점 찾기

2. 검사할 블록 위치 찾기

3. 블록 넣어 가능한지 체크

4. 블록 지우기

5. 지울 블록이 없을 때까지 2~4 반복

 

 

1. 각 블록을 포함하는 가장작은 사각형의 가장왼쪽,위 점 찾기 - set_squre_edge

나는 사용할 수 있는 블록 5개를 배열로 그렸다.

이를 맵의 블록에 1대1로 확인해야하기 때문에 사각형의 좌표가 필요하다.

위의 저 모양의 블록을 배열로 만들면 아래와 같다.

[0,0,1]

[1,1,1]

이 배열을 맵에서 찾은 블록과 매칭 시켜봐야한다. 그래서 저 빨간 사각형의 좌표가 필요한 것이다.

이것은 bfs로 진행했고, 가장작은 x,y좌표를 구하면 된다.

이 좌표는 뒤에 3번 과정에서 사용된다.

 

 

2. 검사할 블록 위치 찾기 - search_target

맨 왼쪽 부터 위에서 아래로 블록을 확인한다.

이때 블록이 있다면 해당 블록은 지워질 수도 있는 블록인 것이다.

그래서 다음 3번 과정을 진행한다.

 

3. 블록 넣어 가능한지 체크 - select_block

여기는 1번에서 구한 x,y좌표를 활용한다.

x,y 좌표는 해당 블록을 아우는 사각형의 맨 왼쪽,위 좌표이다.

이 좌표부터 5개의 블록을 하나하나 체크해주면 된다.

이때 두가지를 검사해야한다.

   - 만약 맵에 값이 0이 아니라면 비교해보는 블록의 값은 1이어야한다.

   - 만약 맵에 값이 0이라면 비교해보는 블록의 값도 0이어야한다.

        - 이 경우 위쪽 블록도 모두 확인해봐야한다.

         아래 그림과 같은 상황이다.

          왜냐면 빈칸에 검정 블록이 떨어져야하는데 위에 다른 블록이 막고 있다면 놓을 수 없기 때문이다.

 

4. 블록 지우기

블록 모양대로 맵을 값을 1로 바꿔준다.

 

5. 반복

 2번 과정에서 맵의 모든 칸을 확인했는데 지울 블록을 찾기 못했다면 -1을 리턴하게 되고 이때 종료 된다.

 

from collections import deque

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

blocks = [
    [
        [[1, 0, 0], [1, 1, 1]],
        [[0, 1], [0, 1], [1, 1]]
    ],
    [
        [[1, 0], [1, 0], [1, 1]],
        [[0, 0, 1], [1, 1, 1]],
    ],
    [
        [[0, 1, 0], [1, 1, 1]],
    ]
]

def solution(input_board):
    global board, n, edges
    board = input_board
    n = len(board)
    edges = {}
    answer = 0

    set_squre_edge()

    while True:
        rst = search_target()
        if rst == -1:
            break
        answer += rst
    return answer

def set_squre_edge():
    global edges
    visited = [[False]*n for _ in range(n)]
    for sx in range(n):
        for sy in range(n):
            if board[sx][sy] != 0 and not visited[sx][sy]:
                edges[board[sx][sy]] = bfs(sx,sy,visited)

def bfs(sx,sy,visited):
    visited[sx][sy] = True
    q = deque([(sx, sy)])
    min_x, min_y = sx, sy
    typ = board[sx][sy]
    while q:
        x, y = q.pop()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if boundray_validator(nx,ny) and not visited[nx][ny] and board[nx][ny] == typ:
                min_x = min(min_x,nx)
                min_y = min(min_y,ny)
                visited[nx][ny] = True
                q.appendleft((nx,ny))
    return (min_x, min_y)

def search_target():
    for y in range(n):
        for x in range(n):
            if board[x][y] > 0:
                sx,sy = edges[board[x][y]]
                if select_block(sx, sy, board[x][y]):
                    return 1
                else:
                    break
    return -1

def select_block(sx, sy, typ):
    for i in range(3):
        for j in range(len(blocks[i])):
            block = blocks[i][j]
            if is_possible(sx, sy, block, typ):
                remove_block(sx, sy, block)
                return True
    return False


def remove_block(sx, sy, block):
    global board
    r, c = len(block), len(block[0])
    for x in range(sx, sx + r):
        for y in range(sy,sy + c):
            board[x][y] = 0


def is_possible(sx, sy, block, typ):
    r, c = len(block), len(block[0])
    for x in range(r):
        for y in range(c):
            tx, ty = sx + x, sy + y
            if boundray_validator(tx, ty):
                if (board[tx][ty] == typ and block[x][y] == 1):
                    continue
                elif (board[tx][ty] == 0 and block[x][y] == 0):
                    for nx in range(tx-1,-1,-1):
                        if board[nx][ty] != 0:
                            return False
                else:
                    return False
            else:
                return False


    return True


def boundray_validator(x, y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    return True