문제
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
Plain Text
복사
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력
•
입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
•
2 ≦ n, m ≦ 30
•
board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
예시
정답
import numpy as np
# 없앨 블록의 위치 저장
def delete_stack(i,j,delete_list):
if [i,j] not in delete_list:
delete_list.append([i,j])
# 블록 없애기: return 값 = 없어진 블록 갯수
def delete_step(m,n,matrix,delete_list):
for i in range(m-1):
for j in range(n-1):
current = matrix[i,j]
right = matrix[i+1,j]
below = matrix[i,j+1]
diag = matrix[i+1,j+1]
if (current != None) & (current == right) & (current == below) & (current == diag):
delete_stack(i,j,delete_list)
delete_stack(i+1,j,delete_list)
delete_stack(i,j+1,delete_list)
delete_stack(i+1,j+1,delete_list)
if len(delete_list) == 0: # 없앨 블록이 없는 경우
return 0
else:
deleted = len(delete_list) # 없어진 블록 갯수
# 블록 없애기
for d in delete_list:
matrix[d[0], d[1]] = None
# 블록 내리기
for i in range(n):
temp = list(matrix[:,i])
None_cnt = temp.count(None)
# None 값 맨 위로 보내기
while None in temp:
temp.remove(None)
new_temp = [None]*None_cnt + temp
matrix[:,i] = new_temp
return deleted
def solution(m,n, board):
# numpy matrix로 만들기
matrix = np.full((m,n), None)
for i in range(m):
for j in range(n):
matrix[i,j] = board[i][j]
# 블록 없애기 게임
cnt = 0
delete_list = []
deleted = delete_step(m, n, matrix, delete_list) # 없어진 블록의 갯수
cnt += deleted
# 블록 없애기 반복
while deleted!=0:
delete_list = []
deleted = delete_step(m, n, matrix, delete_list)
cnt += deleted
return cnt
Python
복사
풀이
•
우선 인덱싱을 편하게 하기 위해 주어진 문자열을 numpy matrix로 만들자.
def solution(m,n, board):
# numpy matrix로 만들기
matrix = np.full((m,n), None)
for i in range(m):
for j in range(n):
matrix[i,j] = board[i][j]
Python
복사
•
그 다음 블록을 없애는 function을 만들어주었다.
•
우선 없어질 블록의 위치를 전부 찾고나서 블록을 한 번에 없애주는 방법을 사용하였다.
•
사라질 블록의 위치를 찾고 없애는 방법은 다음과 같다.
1.
왼쪽 위에서부터 오른쪽 아래까지 블록을 하나씩 살펴본다.
def delete_step(m,n,matrix,delete_list):
for i in range(m-1):
for j in range(n-1):
Python
복사
2.
현재 블록에서(current) 오른쪽(right)과 밑(below) 그리고 오른쪽 대각선(diag)의 원소가 같은 경우 사라질 블록 리스트(delete_list)에 추가한다.
# 없앨 블록의 위치 저장
def delete_stack(i,j,delete_list):
if [i,j] not in delete_list:
delete_list.append([i,j])
# 블록 없애기: return 값 = 없어진 블록 갯수
def delete_step(m,n,matrix,delete_list):
for i in range(m-1):
for j in range(n-1):
current = matrix[i,j]
right = matrix[i+1,j]
below = matrix[i,j+1]
diag = matrix[i+1,j+1]
if (current != None) & (current == right) & (current == below) & (current == diag):
delete_stack(i,j,delete_list)
delete_stack(i+1,j,delete_list)
delete_stack(i,j+1,delete_list)
delete_stack(i+1,j+1,delete_list)
Python
복사
3.
원소를 전부 살펴본 이후 사라질 블록 리스트(delete_list)에 있는 원소들을 전부 None 값으로 바꾼다.
# 블록 없애기
for d in delete_list:
matrix[d[0], d[1]] = None
Python
복사
4.
None 값을 맨 위로 보낸다.
# 블록 내리기
for i in range(n):
temp = list(matrix[:,i])
None_cnt = temp.count(None)
# None 값 맨 위로 보내기
while None in temp:
temp.remove(None)
new_temp = [None]*None_cnt + temp
matrix[:,i] = new_temp
Python
복사
5.
더 이상 없어질 블록이 없어질 때까지 반복한다.
# 블록 없애기 게임
cnt = 0
delete_list = []
deleted = delete_step(m, n, matrix, delete_list) # 없어진 블록의 갯수
cnt += deleted
# 블록 없애기 반복
while deleted!=0:
delete_list = []
deleted = delete_step(m, n, matrix, delete_list)
cnt += deleted
return cnt
Python
복사