[python] 프로그래머스 - 블록 게임(2019 KAKAO BLIND RECRUITMENT)

🤔문제 해결

Lv 4 | 시뮬레이션?

 

먼저 지울 수 없는 블록과 지울 수 있는 블록으로 나눴다. 동그라미 친 블록은 지울 수 있는 블록

board 의 맨위 왼쪽부터 차례로 탐색한다.

블록을 만나면 위에 동그라미 친 블럭인지 확인하고,

맞다면 지울 수 있는지 확인한다.

지울 수 있다면 지워주고, 지울 수 없다면( 지울 수 있는 블록이긴 한데 위에가 막혀서 아직 못지움) 임시 리스트에 저장.

다음 블록들을 지우는 것을 성공할 때마다 임시저장한 블록들도 지울 수 있는지 같이 체크해서 지워준다.

 

💨 문제는 크게 어렵지 않지만, 어떻게든 풀 수 있을 것이다. 시간이 오래걸리겠지만...

 

💻소스 코드

blocks = {
    1: [[
        (1, 0),
        (1, 1),
        (1, 2)
    ],
        [(0, 1), (0, 2)]]
    ,

    2: [[
        (1, 0),
        (1, -1),
        (1, -2)
    ],
        [(0, -1), (0, -2)]],
    3: [[
        (1, 0),
        (2, 0),
        (2, 1)
    ],
        [(1, 1)]],
    4: [[
        (1, 0),
        (2, 0),
        (2, -1)
    ],
        [(1, -1)]],
    5: [[
        (1, 0),
        (1, -1),
        (1, 1)
    ],
        [(0, -1), (0, 1)]],
}


def solution(board):
    answer = 0
    n = len(board)

    # 지울 수 있는 블록인지 아닌지 체크
    def block_check(x, y, idx):
        for block, d in blocks.items():
            for k in range(3):
                nx = x + d[0][k][0]
                ny = y + d[0][k][1]
                if 0 <= nx < n and 0 <= ny < n:
                    if board[nx][ny] != idx:
                        break
                else:
                    break
            else:
                return block
        else:
            return 0

    # 지우러 들어가기 먼저 체크부터하고
    def remove_check(x, y, shape, idx):
        nonlocal answer
        for dx, dy in blocks[shape][1]:
            cx = x + dx
            cy = y + dy
            while cx >= 0:
                if board[cx][cy] == 0:
                    cx -= 1
                else:
                    # 못 지움 - 위가 다른 블록으로 막혀있음
                    if idx not in temp_list:
                        temp_list.add(idx)
                        temp_dict[idx] = [x, y, shape]
                    return False

        else:
            # 지울 수 있는 조건을 만족해서 지우기
            board[x][y] = 0
            for k in range(3):
                board[x + blocks[shape][0][k][0]][y + blocks[shape][0][k][1]] = 0
            answer += 1
            return True

    never_list = set()  # 블록이 아예 못지우는 형태
    temp_list = set()  # 지울 수 있는 블럭이지만 가로막혀서 못지우고 있는 애
    temp_dict = {}  # 그 애의 초기 위치

    # 시작!! - 블록 찾기
    for i in range(n):
        for j in range(n):
            K = board[i][j]
            if K and K not in never_list and K not in temp_list:
                shape = block_check(i, j, K)
                if shape:  # 내가 원하는 블록(지울 수 있는 블록) 이면
                    if remove_check(i, j, shape, K):  # 지울 수 있는지 체크하러 ㄱㄱ
                        if temp_list:  # 못 지웠떤 애들 다시 지워볼까?
                            for key, value in temp_dict.items():
                                if key in temp_list:
                                    remove_check(value[0], value[1], value[2], key)
                                    temp_list.remove(key)
                else:
                    never_list.add(K)

    return answer


# print(solution([[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, 0, 0, 0, 0],
#                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 4, 0, 0, 0], [0, 0, 0, 0, 0, 4, 4, 0, 0, 0],
#                 [0, 0, 0, 0, 3, 0, 4, 0, 0, 0], [0, 0, 0, 2, 3, 0, 0, 0, 5, 5], [1, 2, 2, 2, 3, 3, 0, 0, 0, 5],
#                 [1, 1, 1, 0, 0, 0, 0, 0, 0, 5]]))

# print(solution([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#                 [4, 0, 7, 0, 0, 0, 0, 0, 0, 0],
#                 [4, 7, 7, 7, 0, 0, 0, 0, 0, 0],
#                 [4, 4, 0, 0, 0, 0, 0, 0, 0, 0],
#                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#                 [0, 0, 0, 0, 3, 0, 0, 0, 0, 0],
#                 [0, 0, 0, 2, 3, 0, 0, 0, 5, 5],
#                 [1, 2, 2, 2, 3, 3, 0, 0, 0, 5],
#                 [1, 1, 1, 0, 0, 0, 0, 0, 0, 5]]))

 

📕문제 확인

출처: 프로그래머스

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

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

---

문제 설명

블록게임

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

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

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

게임규칙

아래 그림과 같이 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에 놓여있는 각 블록은 숫자를 이용해 표현한다.
  • 잘못된 블록 모양이 주어지는 경우는 없다.
  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

---

입출력 예

 

board	result
[[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,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]	2