문제
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
1.
만약 판이 위와 같이 주어질 경우, 라이언(R)이 2×2로 배치된 7개 블록과 콘(C)이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
2-1.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
2-2.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력 형식
- 입력으로 판의 높이
m, 폭n과 판의 배치 정보board가 들어온다. - 2 ≦
n,m≦ 30 board는 길이n인 문자열m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
입출력 예
| m | n | board | answer |
|---|---|---|---|
| 4 | 5 | ["CCBDE", "AAADE", "AAABF", "CCBBF"] | 14 |
| 6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
사용 코드
def board_remove(board, remove_elements):
for i,j in remove_elements: # [1,1], [2,4]
board[i].pop(j)
return board, len(remove_elements)
def search_board( board):
i, j = -1, 1
remove_elements = []
# 전체 board를 순회해야 한다.
while i < len(board)-2 :
i+=1
tmp_i = list(map(lambda x: x + i, [0, 0, 1,1]))
j = len(board[i])
while j > 1 :
set_block = set(); j -=1
if j > len(board[i+1])-1: continue
tmp_j = list(map(lambda x: x + j, [0, -1, 0,-1]))
for t_i, t_j in zip(tmp_i, tmp_j) :
set_block.add( board[t_i][t_j] )
if len(set_block) >=2 : # 중복되지 않은 값이 존재시
break
if len(set_block) == 1 : # 모든 값 중복 경우
# 삭제되어야 하는 block는 계속 쌓인다.
cnt_blocks = [ (t_i, t_j) for t_i, t_j in zip(tmp_i, tmp_j) ]
remove_elements = list(set(remove_elements+cnt_blocks))
# while이 끝난 경우 (모든 board를 탐색 완료한 경우)
return len(set(remove_elements)) > 0, sorted(remove_elements, key =lambda x:(x[0],x[1]) ,reverse=True)
def solution(m, n, board):
# board를 90도 회전 시킨다.
rot_board = [[ board[m][n] for m in reversed(range(m)) ] for n in range(n) ]
answer = 0
while True :
# board의 행의 마지막 부분, 열의 시작부분 돌지 않게 만들기
is4Block, remove_elements = search_board( rot_board)
if is4Block : # remove 되어야 하는 block이 존재
rot_board,count = board_remove(rot_board, remove_elements)
answer += count
else : # 전체를 순회 했는데 remove elements가 없는 경우
break
return answer코드 설명
1. board 판을 90도 회전시킨다.
board의 끝이 리스트의 끝으로 이동이 된다.
pop를 사용해서 자동으로 떨어지는 부분을 구현할 수 있다.
2. board 전체를 순회한 후 조건에 맞는 block들을 지워야 한다.
조건 중에 같은 elements를 공유해도 2x2 조건에 맞으면 같이 사라진다는 얘기를 충족시킬 수 있다.
- 위의 2가지 조건이 가장 큰 핵심 조건이므로 이 조건들을 만족하는 코드를 구현한다.
함수 설명
board_remove : 전체 board와 삭제되어야 하는 block들의 index를 가지고 있는 remove_elements를 parameter로 받은 후 전체 board에서 삭제되어야 하는 index를 pop 합니다.
search_board : 현재 주어진 board에서 삭제 가능한 block들을 있는 경우 True 없는 경우 False를 반환합니다.
그리고 remove_elements 내부의 값들을 key =lambda x:(x[0],x[1]) ,reverse=True 조건으로 정렬한 후 반환합니다.
- [0][0]과 [1][0]의 경우 [0][0]이 먼저 제거 되어야 index 오류가 발생하지 내림차순 정렬을 하게 만들었습니다.
