카카오 블라인드 채용

[카카오] 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 카카오 블라인드 채용 블록 게임

admin

Recent Posts

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

2일 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

1개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

1개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

1개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

2024년 9월 1일 일요일 – 서울 생활 118주차

여행 지난주에 코로나에 걸리는 바람에 근 3주만에 가족을 만나고 왔다. 집에 있어봐야 시간도 안가고 할…

2개월 ago

This website uses cookies.