[프로그래머스] 🎮 블록 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

[프로그래머스] 🎮 블록 게임 - 2019 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

문제 설명

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다.

이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

제한사항

• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
• N은 4 이상 50 이하다.
• board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
• 0 은 빈 칸을 나타낸다.
• board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
• 잘못된 블록 모양이 주어지는 경우는 없다.
• 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
• 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

😃 나의 풀이

n = 0
dx = [[0,0,0,1,1,1], [0,0,1,1,2,2]]
dy = [[0,1,2,0,1,2], [0,1,0,1,0,1]]

def safe(x, y, n):
    return min(x,y) >= 0 and max(x,y) < n

def possible(x, y, k, count, matrix, check, n):
    col = -1
    cur = 0
    for i in range(6):
        nx = x + dx[k][i]
        ny = y + dy[k][i]
        if safe(nx, ny, n):
            if matrix[nx][ny]:
                if col == -1:
                    col = matrix[nx][ny]
                else:
                    if col != matrix[nx][ny]:
                        return count, matrix, check, False
            else:
                cur += 1
                if count[nx][ny]:
                    return count, matrix, check, False
        else:
            return count, matrix, check, False
    if cur != 2:
        return count, matrix, check, False
    for i in range(6):
        nx = x + dx[k][i]
        ny = y + dy[k][i]
        check[nx][ny] = True
    return count, matrix, check, True

def solution(board):
    n = len(board)
    answer = 0
    count = [[0 for i in range(n)] for j in range(n)]
    check = [[0 for i in range(n)] for j in range(n)]
    while True:
        for i in range(n):
            for j in range(n):
                count[i][j] = check[i][j] = 0
        flag = False
        for i in range(n):
            for j in range(n):
                if board[i][j] > 0:
                    count[i][j] = 1
                else: count[i][j] = 0
        for i in range(1,n):
            for j in range(n):
                count[i][j] += count[i-1][j]
        for i in range(n):
            for j in range(n):
                for k in range(2):
                    count, board, check, possi = possible(i,j,k,count,board,check, n)

                    if possi:
                        flag = True
                        answer += 1
        for i in range(n):
            for j in range(n):
                if check[i][j]:
                    board[i][j] = 0
        if not flag:
            break
    return answer

이 문제는 3개의 행렬을 사용해서 풀었습니다. 첫 행렬인 board는 기존에 있는 board와 같으며, 블록이 지워지면 이를 반영하여 board가 바뀝니다. 두 번째 행렬은 count입니다. 검은 블록이 위에서 올라오기 때문에 블록 아래에 검은 블록이 오는 경우를 제외하기 위한 행렬입니다. 위에서 부터 값을 가산하면서 해당 행렬을 만들어줍니다. 세 번째 행렬은 지워야 할 block을 알려줄 check 행렬입니다.

문제 풀이 방법에 대해서 설명하겠습니다. 우선 board를 이용하여 count에 대한 행렬을 만듭니다. 그리고 행렬의 모든 위치를 돌면서, 적합한 2 X 3 블록이나 3 X 2 블록이 있는 지 확인하기위해 possible 함수를 사용합니다. possible 함수에서는 2 X 3 블록과 3 X 2 블록의 확인을 위해 dx와 dy라는 새로운 행렬을 이용해서 검증을 했습니다. 또한 인덱스에서 벗어나는 경우를 방지하기 위해 safe라는 함수를 만들어 예외의 경우가 없게 합니다. 그 아래 코드는 board에서 2 X 3 혹은 3 X 2 의 크기를 가진 행렬 중에 같은 숫자가 4개 있고 0이 2개 있는 곳을 찾습니다. 여기서 만이 board에서 0인 곳이 count에서 0이 아니라면 블록 아래 있다는 뜻이므로 False를 반환합니다. 이렇게 코드를 짜게되면 여기에 나오지 않은 테트리스의 기본 블록인 나머지 두 블록을 생각할 필요가 없습니다. 이미 board에 있는 2 X 3 블록과 3 X 2 블록을 비교하기 때문에 나머지 블록의 경우는 나올 수 가 없게 됩니다. 블록이 지워질 수 있다는 것이 판명되면 check 행렬을 업데이트하고 board를 check 행렬을 이용해 업데이트합니다. 또한 플래그를 이용하여 현재 시행에서 블록이 지워졌는 지를 판별하여 게임이 마무리 되게 합니다.

또 하루를 날린 문제입니다 😂 과거 JAVA를 이용해서 비슷한 문제를 BOJ에서 풀었는데, 그 보다 더 어려운 느낌이었습니다. 다른 풀이를 못올리는 이유는 다른 코드들이 너무 길고, 대부분이 numpy모듈을 사용해서 코드를 해석하는 데 시간이 오래 걸리기 때문이었습니다. 확실히 numpy를 사용한 코드가 사용하지 않은 코드에 비해 짧아서 numpy에 대한 공부도 필요하다고 느꼈습니다.