반응형
https://programmers.co.kr/learn/courses/30/lessons/42894
코딩테스트 연습 - 블록 게임
[[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
programmers.co.kr



구현까지 시간이 오래 걸렸던 문제.
검은 블록을 채울 수 있는 모든 공간에 검은 블록을 채우고,
검은 블록과 설치된 블록을 합쳤을 때 직사각형 블록이 나올 수 있는지를 검사한다.
특징이라면, 제거 가능한 직사각형 블록이 되기 위해서는
직사각형 밑변에 해당하는 부분은 반드시 설치된 블록이어야 한다는 것.
그러므로, 배열 가장 아래에서부터 순회하며 '설치된 블록'의 길이가 2 또는 3일 경우 직사각형 블록 여부를 검사하는 식으로 해결했다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 블록이 직사각형인지 | |
def check_shape(start, color, row_num, board): | |
y, x = start | |
color = board[y][x] | |
coord = set() | |
color_cnt, black_cnt = 0, 0 | |
if row_num == 2 and y - 2 >= 0: | |
# [1,#], | |
# [1,#], | |
# [1,1] 와 같은 형태 | |
for cx in range(x, x-2, -1): | |
for cy in range(y, y-3, -1): | |
if cy >= 0 and (board[cy][cx] == color or board[cy][cx] == '#'): | |
if board[cy][cx] == color: color_cnt += 1 | |
if board[cy][cx] == '#': black_cnt += 1 | |
coord.add((cy, cx)) | |
else: | |
return None | |
if color_cnt == 4 and black_cnt == 2: | |
return coord | |
else: | |
return None | |
# [1,0,0], | |
# [1,1,1] 와 같은 형태 | |
if row_num == 3 and y-1 >= 0: | |
for cx in range(x, x-3, -1): | |
for cy in range(y, y-2, -1): | |
if cy >= 0 and (board[cy][cx] == color or board[cy][cx] == '#'): | |
if board[cy][cx] == color: color_cnt += 1 | |
if board[cy][cx] == '#': black_cnt += 1 | |
coord.add((cy, cx)) | |
else: | |
return None | |
# 블록 개수 4개, 검은 블록 2개일 경우에만 제거 가능. | |
if color_cnt == 4 and black_cnt == 2: | |
return coord | |
else: | |
return None | |
return None | |
# 검은 블록을 채워넣는 함수 | |
def build(board): | |
for x in range(len(board[0])): | |
for y in range(len(board)): | |
if board[y][x] == '#': | |
continue | |
if board[y][x] == 0: | |
board[y][x] = '#' | |
elif board[y][x] != 0: | |
break | |
# 전체 배열을 순회하면서, 직사각형 조건에 맞는지 확인하는 함수 | |
def search_shape(board): | |
for y in range(len(board)-1, -1, -1): | |
consecutive = 0 | |
color = None | |
for x in range(len(board[0])): | |
# 빈 공간일 경우 | |
if board[y][x] == 0: | |
color = None | |
consecutive = 0 | |
continue | |
# 검은 블록을 # 로 설정했기 때문에, type()이 int이면서 0이 아닌 블록 = 설치된 블록 | |
if type(board[y][x]) is int and board[y][x] != 0: | |
if color == None: | |
consecutive = 1 | |
color = board[y][x] | |
continue | |
if board[y][x] != color: | |
color = board[y][x] | |
consecutive = 1 | |
continue | |
if color == board[y][x]: | |
consecutive += 1 | |
# 가로 | |
if 2 <= consecutive <= 3: | |
coord = check_shape((y,x), color, consecutive, board) | |
if coord is not None: | |
return coord | |
return None | |
# 블록 제거 | |
def remove(board, coord): | |
for y, x in coord: | |
board[y][x] = 0 | |
def solution(board): | |
cnt = 0 | |
while True: | |
# 1. 조건상 채울 수 있는 모든 공간에 검은 블록 채워넣기 | |
build(board) | |
# 2. 검은 블록 + 블록으로 제거될 수 있는 블록 찾기 | |
coord = search_shape(board) | |
# 찾을 수 없는 경우 break | |
if coord is None: | |
break | |
# 제거 블록개수 + 1 | |
cnt += 1 | |
# 블록 제거하기 | |
remove(board, coord) | |
return cnt |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] 백준 19236. 청소년 상어 (0) | 2020.07.06 |
---|---|
[Python] 백준 17144. 미세먼지 안녕! (0) | 2020.05.20 |
[Python] 백준 15684. 사다리 조작 (0) | 2020.05.18 |
[Python] 백준 11003. 최솟값 찾기 (0) | 2020.05.16 |
[Python] 프로그래머스. 소수 만들기 (Level 2) (0) | 2020.05.11 |