[1차] 프렌즈4블록
import numpy as np
def solution(m, n, board):
board_list = np.array([list(map(ord, x)) for x in board])
answer = 0
while True :
zero_list = set()
for h in range(m-1) :
for w in range(n-1) :
if board_list[h, w] == board_list[h, w+1] == board_list[h+1, w] == board_list[h+1, w+1] and board_list[h:h+2, w:w+2].sum() != -4:
zero_list.add((h, w))
zero_list.add((h, w+1))
zero_list.add((h+1, w))
zero_list.add((h+1, w+1))
for h, w in zero_list :
board_list[h, w] = -1
for w in range(n) :
for h in range(m) :
if board_list[h, w] == -1 :
tmp = board_list[:h,w].copy()
board_list[0,w] = -1
board_list[1:h+1,w] = tmp
if answer == len(board_list[board_list == -1]) :
return len(board_list[board_list == -1])
else :
answer = len(board_list[board_list == -1])
풀이
board를2x2크기로 훑으며 4개의 숫자가 다 같으면 빵꾸를 내고 빵구 갯수를 센다(나는-1로 빵꾸처리했음)구멍난 부분을 내리면서 매꿔준다.
알고리즘은 간단한데 익덱싱이 매우 빡세다. 왜냐하면 열 단위로 구멍을 매꾸어야하기 때문임. 그래서 본인은 numpy를 썼는데 지금와서 드는 생각이 아싸리 배열을 시계방향으로 회전시켜놓으면 행단위로 구멍 처리를 할 수 있어서 편했을텐데 하는 생각이 든다. 지금 문제를 푸는 사람은 np.array(list(zip(*board[::-1]))) 로 배열 회전시켜놓고 푸시길
배열 검사
일단 본인은 알파벳을 아스키코드 숫자로 다 바꿨다. 원소끼리 대소관계 비교할필요가 없어서 바꿀필요없긴한데 왜그랬는지는 모르겠음ㅋ
사진에서 보여지듯이 배열 전체를 검사 다 마친후에 구멍을 뚫어야한다. 그래서 구멍을 뚫을 인덱스를 저장해놓고 검사가 마치면 뚫는데 겹치는 인덱스가 있을 수 있으므로(사진처럼) set에 배열을 저장했다가 처리한다.
내리기
배열을 땡겨서 구멍을 매꾸는 작업을 해야하는데 한줄씩 밑으로 내려가며 -1이 나오면 그 위에 있는 배열들을 한칸씩 밑으로 땡기고 제일 위를 -1로 채웠다.
루프 탈출
한바퀴 돌았음에도 빈칸(-1)의 갯수가 같으면 return