728x90
반응형

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 시뮬레이션 문제이고 블럭을 떨어뜨리는 로직을 구현하는 것이 핵심이다.
def solution(m, n, board):
"""블럭을 제거하는 함수"""
def delete_blocks(m, n, board):
# 모든 블럭에 대하여 삭제 조건 검사
deleted_blocks = set()
for x in range(m - 1):
for y in range(n - 1):
point = board[x][y]
if point == '':
continue
# 2*2 영역이 같은 블럭이라면 삭제 블럭 집합에 추가
if (board[x][y] == board[x+1][y] == board[x][y+1] == board[x+1][y+1] == point):
for i in range(2):
for j in range(2):
deleted_blocks.add((x+i, y+j))
# 블럭 삭제
for x, y in deleted_blocks:
board[x][y] = ''
# 삭제한 블럭 개수 리턴
return len(deleted_blocks)
"""블럭을 떨어뜨리는 함수"""
def drop_blocks(m, n, board):
# 열(Column) 단위로 진행
for y in range(n):
# 비어있지 않은 모든 블럭을 수집
blocks = []
for x in range(m):
if board[x][y] != '':
blocks.append(board[x][y])
board[x][y] = ''
# 아래쪽부터 역순으로 배치
x_idx = m - 1
while len(blocks) > 0:
board[x_idx][y] = blocks.pop()
x_idx -= 1
"""메인 로직"""
# board를 2차원 리스트 형태로 변환
board = [list(row) for row in board]
result = 0
while True:
# 더이상 블록을 제거할 수 없다면 종료
count = delete_blocks(m, n, board)
if count == 0:
break
# 제거한 블록 개수 갱신
result += count
# 블록 떨어뜨리기
drop_blocks(m, n, board)
return result
문제에 주어진 내용을 그대로 구현하면 된다. 완전탐색을 진행하면 되며, 최대 30 * 30이기 때문에 시간 초과 날 걱정은 없다.
모든 블럭을 기준으로 2*2 공간을 전부 다 검사하여 제거한다. 단 제거할 블럭을 검사하는 것과 삭제하는 로직은 분리해야 한다. 찾자마다 제거해 버리면 여러 공간에 포함된 블럭이 먼저 제거되어 버려 다음 검사되는 블럭은 제거되지 않을 수 있다. 따라서 제거할 블럭을 전부 찾은 후에 제거는 따로 진행한다.
그리고 블럭을 떨어뜨리는 로직을 구현해야 한다. 행이 아닌 열 단위로 진행하되, 열에 존재하는 모든 블럭을 수집 후 가장 아래쪽부터 차례대로 배치하면 된다. 중력을 구현하는 가장 간단한 방법이다.
이렇게 완성된 제거+떨어뜨리기 2가지를 while문으로 반복하며 제거한 블록의 개수를 세고, 더 이상 제거할 수 없을 때 while문을 종료하면 해결할 수 있다.
728x90
반응형
'Algorithm > Implementation' 카테고리의 다른 글
[백준 10431 / Python / 실버5] 줄세우기 (0) | 2025.06.18 |
---|---|
[프로그래머스 / python / Level 2] 압축 (0) | 2025.06.13 |
[프로그래머스 / python / Level 3] 자물쇠와 열쇠 (0) | 2025.06.11 |
[프로그래머스 / python / Level 1] 가장 많이 받은 선물 (0) | 2025.05.29 |
[Baekjoon 2002 / Python / 실버1] 추월 (1) | 2025.01.22 |