[프로그래머스 > Lv4] 블록 게임

프로그래머스

 

1. 문제

[입력]

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board

 

[결과]

검은 블록을 떨어드려 없앨 수 있는 블록 개수의 최댓값을 return

 

2. 풀이

Lv4 문제들 중 이렇게 알고리즘을 하나도 사용하지 않는 문제들이 더 어려웠던거 같습니다. 😭

말 그대로 알고리즘 없이 모든 경우를 탐색해보면 결과를 얻을 수 있는 문제입니다.

 

처음으로 각 도형들의 모양을 알아낼 필요가 있습니다.

그래서 저는 깊이 우선 탐색을 이용해 각 도형들의 좌표값들을 구하고 각 도형들을 배열에 저장하는 코드를 작성했어요.

 

정말 다행히도, 각 도형들이 모양에 상관없이 모두 다른 숫자로 표현되어 쉽게 구별할 수 있습니다.🙏

# block 모양을 result에 담아 반환
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def getBlock(result,x,y,board,size):
    shape = board[x][y]
    board[x][y]=0
    result.append((x,y))
    
    for d in range(4):
        nx,ny = x+dx[d],y+dy[d]
        if 0<=nx<size and 0<=ny<size and board[nx][ny]==shape:
            getBlock(result,nx,ny,board,size)​

 

이를 2중 for문을 이용해 blocks 배열에 append 시켜주면 아래와 같습니다.

size = len(board)

blocks = []
for x in range(size):
    for y in range(size):
        if board[x][y]!=0:
            block = []
            getBlock(block,x,y,board,size)
            blocks.append(block)

 

그 다음은 각 block들을 순회하며 해당 블록을 제거할 수 있는지 확인하는 작업이 필요합니다. 🤗

주어진 12개의 도형들을 보면 위에서 검은색 블록을 채워넣어 직사각형을 만들 수 있는 도형은 아래 5가지 뿐입니다.

그리고 추가적으로 자신의 블록 위에 제거되지 못하는 블록이 있을 때 또한 제거되지 못하므로, 이를 고려해줄 필요가 있습니다.

 

저는 이를 위해 disableColumn이라는 배열을 사용하였습니다. 😌

disableColumn[i]는 i번째 열에서 제거될 수 없는 블록 중 가장 위에 위치한 블록의 x좌표입니다.

위와 같이 되어 있는 경우에 disableColumn[2]는 1입니다.

특정 block을 직사각형으로 만들기 위해 필요한 열의 disableColumn이 자신의 x좌표보다 작을 경우에는, 자신의 위에 제거되지 못한 블록이 있다는 의미이므로, 해당 block은 제거될 수 없다는 것을 알 수 있습니다. 🤗

 

이를 코드로 표현하면!

def checkRemovable(block, disableColumn):
    x, y = block[0]
    vector = []
    for i in range(4):
        vector.append((block[i][0]-x,block[i][1]-y))
    
    if vector == [(0,0),(1,0),(1,1),(1,2)]:
        return disableColumn[y+1] > x and disableColumn[y+2] > x
    if vector == [(0,0),(1,0),(2,0),(2,-1)]:
        return disableColumn[y-1] > x+1
    if vector == [(0,0),(1,0),(2,0),(2,1)]:
        return disableColumn[y+1] > x+1
    if vector == [(0,0),(1,0),(1,-1),(1,-2)]:
        return disableColumn[y-1] > x and disableColumn[y-2] > x
    if vector == [(0,0),(1,0),(1,1),(1,-1)]:
        return disableColumn[y-1] > x and disableColumn[y+1] > x
    return False

 

3. 코드

Python

def solution(board):
    answer = 0
    size = len(board)
    
    blocks = []
    disableColumn = [size+1]*size
    for x in range(size):
        for y in range(size):
            if board[x][y]!=0:
                block = []
                getBlock(block,x,y,board,size)
                blocks.append(block)

    disableRemove = -1
    while disableRemove != 0:
        disableRemove = 0
        temp = []
        for block in blocks:
            able = checkRemovable(block, disableColumn)
            if able: temp.append(block)
            else:
                for x, y in block:
                    if disableColumn[y] > x:
                        disableColumn[y] = x
                disableRemove+=1
        blocks = temp
        
    return len(blocks)

# block 모양을 result에 담아 반환
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def getBlock(result,x,y,board,size):
    shape = board[x][y]
    board[x][y]=0
    result.append((x,y))
    
    for d in range(4):
        nx,ny = x+dx[d],y+dy[d]
        if 0<=nx<size and 0<=ny<size and board[nx][ny]==shape:
            getBlock(result,nx,ny,board,size)
            
    
def checkRemovable(block, disableColumn):
    x, y = block[0]
    vector = []
    for i in range(4):
        vector.append((block[i][0]-x,block[i][1]-y))
    
    if vector == [(0,0),(1,0),(1,1),(1,2)]:
        return disableColumn[y+1] > x and disableColumn[y+2] > x
    if vector == [(0,0),(1,0),(2,0),(2,-1)]:
        return disableColumn[y-1] > x+1
    if vector == [(0,0),(1,0),(2,0),(2,1)]:
        return disableColumn[y+1] > x+1
    if vector == [(0,0),(1,0),(1,-1),(1,-2)]:
        return disableColumn[y-1] > x and disableColumn[y-2] > x
    if vector == [(0,0),(1,0),(1,1),(1,-1)]:
        return disableColumn[y-1] > x and disableColumn[y+1] > x
    return False