문제 설명 및 제한사항
문제 설명
프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.
이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.
프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.
게임규칙
아래 그림과 같이 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에 놓여있는 각 블록은 숫자를 이용해 표현한다.
◦
잘못된 블록 모양이 주어지는 경우는 없다.
◦
모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
◦
예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.
아이디어 및 해결 방법
코드
from copy import deepcopy
def above_is_empty(board, r, c):
return all(board[_r][c] == 0 for _r in range(r))
def can_remove(board, bid):
R, C = len(board), len(board[0])
rs, cs = [], []
for r in range(R):
for c in range(C):
if board[r][c] == bid:
rs.append(r)
cs.append(c)
# 직사각형 내의 각 위치를 탐색합니다.
for r in range(min(rs), max(rs) + 1):
for c in range(min(cs), max(cs) + 1):
if board[r][c] == bid:
continue
# 채워야 할 빈 공간인데 못 채우는 상황이면 False를 리턴합니다.
if board[r][c] != 0 or not above_is_empty(board, r, c):
return False
return True
def remove(board, bid):
R, C = len(board), len(board[0])
for r in range(R):
for c in range(C):
if board[r][c] == bid:
board[r][c] = 0
return board
def solution(board):
R, C = len(board), len(board[0])
answer = 0
prev_board = None
# 더이상 제거할 블록이 없을 때까지 반복합니다.
while board != prev_board:
prev_board = deepcopy(board)
# 맨 왼쪽부터 하나씩 1x1 정사각형을 떨어뜨려 봅니다.
removed = False
for c in range(C):
r = 0
# 내려갈 수 있는 만큼 내려갑니다.
while r < R and board[r][c] == 0:
r += 1
# 마지막 행에 도달하면 빈 열이라는 뜻입니다. 건너뜁니다.
if r == R:
continue
bid = board[r][c]
if can_remove(board, bid):
board = remove(board, bid)
removed = True
break
if removed:
answer += 1
return answer
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges