[카카오] 2019 KAKAO BLIND RECRUITMENT 1차 풀이 – 블록 게임
이 포스팅에서는 2019 카카오 블라인드 채용 1차 문제인 ‘블록 게임’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/42894에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.
공식 풀이는 링크를 참조하시기 바랍니다.
블록 게임
출처 : 2019 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/42894
카테고리 : Bruteforce
난이도 : 보통
문제 설명
보드가 주어지고 보드에 존재하는 각 블록들의 정보가 표시된다. 각각의 블록은 고유한 ID 넘버를 가진다. 우리는 보드의 맨 위에서부터 수직으로 1×1의 검은 블록을 낙하시킬 수 있는데, 이 방식으로 블록을 2 x 3 직사각형으로 채울 수 있으면 해당 블록은 사라진다.
단 여기에서 보드에 주어진 블록이 다른 블록들과 겹쳐져서 2 x 3이 되는 경우에는 사라지지 않는다. 우리가 위에서 떨어뜨린 검은 블록과 합쳐져서 2 x 3이 되는 경우에만 블록이 사라진다.
검은 블록을 무한히 떨어뜨릴 수 있다고 할 때, 최대 몇 개의 블록을 보드에서 제거할 수 있을까.
문제 풀이
모든 블록은 그 유형에 관계없이 공통적으로 2개의 빈 공간을 가지고 그 공간이 채워지면 제거될 수 있다. 즉, 보드에 존재하는 블록에 대해 그 빈 공간에서 보드 최상단까지에 장애물이 없다면 검은 블록을 떨어뜨려 해당 블록을 제거할 수 있다는 말이다.
일단 블록을 찾는 과정은 가능한 블록의 유형에 대해서 가장 상단 좌측의 블록을 (0, 0)으로 기준을 잡고 나머지 블록들을 상대좌표로 기술하여 정의한다. 그리고 보드의 상단 왼쪽에서부터 오른쪽 그리고 아랫 방향으로 탐색을 시작해서 새롭게 발견되는 ID에 대해 그 근처에 같은 ID를 가지는 블록들의 상대좌표를 구한 다음 우정의된 블록 유형에 맞는게 있는지 살핀 후에 매칭되는 것을 찾아낸다.
각 블록에 대해서 이제 시작 좌표를 가지고, 그에 해당하는 빈 공간들의 좌표를 얻어냈다.
모든 블록을 Iteration 하면서 지울 수 있는 것이 있는지 찾고, 존재하면 보드에서 지운 후 카운트를 늘린다. 새롭게 지울 수 없는 것이 있을 때까지 반복한 후 카운트를 출력한다.
정답 코드
# 가능한 블록들의 집합. 블록의 가장 상단을 (0,0)이라 할 때 나머지 블록의 상대 좌표 (y축, x축)으로 기술 # 이 블록이 감싸는 넓이 6의 직사각형에서 블록으로 채워진 부분을 0번 인덱스, 빈 부분을 1번 인덱스에 둔다. possible_blocks = [[[[0, 0], [0, 1], [0, 2], [1, 2]], [[1, 0], [1, 1]]], [[[0, 0], [0, 1], [1, 0], [2, 0]], [[1, 1], [2, 1]]], [[[0, 0], [1, 0], [1, 1], [1, 2]], [[0, 1], [0, 2]]], [[[0, 0], [1, 0], [2, –1], [2, 0]], [[1, –1], [0, –1]]], [[[0, 0], [0, 1], [0, 2], [1, 0]], [[1, 1], [1, 2]]], [[[0, 0], [1, 0], [2, 0], [2, 1]], [[0, 1], [1, 1]]], [[[0, 0], [1, –2], [1, –1], [1, 0]], [[0, –2], [0, –1]]], [[[0, 0], [0, 1], [1, 1], [2, 1]], [[1, 0], [2, 0]]], [[[0, 0], [1, –1], [1, 0], [1, 1]], [[0, –1], [0, 1]]], [[[0, 0], [1, 0], [1, 1], [2, 0]], [[0, 1], [2, 1]]], [[[0, 0], [0, 1], [0, 2], [1, 1]], [[1, 0], [1, 2]]], [[[0, 0], [1, –1], [1, 0], [2, 0]], [[0, –1], [2, –1]]]] # board[x][y]를 지나는 블록이 위의 배열에서 몇 번째 인덱스에 해당하는 블록인지 찾아낸다. def get_block(x, y, board): global possible_blocks pivot = board[x][y] block = [] for i in range(max(0, x – 2), min(len(board), x + 3)): for j in range(max(0, y – 2), min(len(board[0]), y + 3)): if board[i][j] == pivot: block.append([i – x, j – y]) block.sort() for i in range(len(possible_blocks)): candidate = possible_blocks[i] is_equal = True for j in range(4): if candidate[0][j][0] != block[j][0] or candidate[0][j][1] != block[j][1]: is_equal = False break if is_equal: return i return –1 # 현재 블록의 빈 공간들에 대해 보드의 맨 위까지 어떤 다른 블록도 만나지 않고 # 이동할 수 있다면 검은 블록을 떨어뜨려서 채울 수 있다. def can_fill(block, board): for empty_space in block[2]: i = block[0] + empty_space[0] j = block[1] + empty_space[1] while i >= 0 and board[i][j] == 0: i –= 1 if i >= 0: return False return True # 직사각형이 되어 채워진 블록을 보드에서 제거한다 def remove_block_id(removed_block_id, board): for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == removed_block_id: board[i][j] = 0 return def solution(board): global possible_blocks blocks = {} # 보드에 존재하는 블록을 찾아 시작 좌표와 그 타입을 기록한다 for i in range(len(board)): for j in range(len(board[i])): if board[i][j] != 0 and board[i][j] not in blocks: blocks[board[i][j]] = [i, j, get_block(i, j, board)] cnt = 0 while True: # 매 시행마다 최소 하나의 블록을 제거해야한다. removed_block_id = –1 # 모든 블록에 대해 for block_id in blocks: block = blocks[block_id] # 이 블록을 채울 수 있으면 if can_fill([block[0], block[1], possible_blocks[block[2]][1]], board): # 카운트 하고 제거할 블록의 id를 기록한다. cnt += 1 removed_block_id = block_id break if removed_block_id == –1: return cnt # 블록을 제거한다. blocks.pop(removed_block_id) remove_block_id(removed_block_id, board) | cs |
Competition 카카오 블라인드 채용 블록 게임