[Level 2] 프렌즈 4블록 - 17679
구분
코딩테스트 연습 > 카카오 2018 블라인드 1차
풀이 요약
주어진 요건대로 인접한 블록 매트릭스를 제거하는 시뮬레이션 문제. 2차원 배열을 행/열을 바꾸어서 조작하기 쉽게 만들고, 사라진 블럭의 위치를 set함수의 합집합 연산을 이용하여 구하면 된다.
mxn 형태의 보드판이 주어져서 BFS, DFS를 활용해야 하나 고민했는데, 블럭은 무조건 2x2 형식으로 사라지기도 하고 블럭이 위에서 아래로 내려오는 구조라 원소의 행을 바꿔주어야 하기 때문에 배열을 조작하는 것이 올바른 접근법이었다. 배열을 조작하기 다소 까다로운 문제였다.
나의 풀이
def pop_block(board, m, n):
pop_union_set = set()
# 행과 열이 반대인 보드니까
for i in range(1, n):
for j in range(1, m):
if board[i][j] == board[i-1][j-1] == board[i][j-1] == board[i-1][j] != '펑':
# 합집합 만들기
pop_union_set |= set([(i,j),(i-1,j-1),(i,j-1),(i-1,j)])
for i,j in pop_union_set:
board[i][j] = 0
# 터져서 사라진 블록을 메꾸는 작업
for i, row in enumerate(board):
empty_list = ['펑'] * row.count(0)
board[i] = empty_list + [block for block in row if block != 0]
return len(pop_union_set)
def solution(m, n, board):
"""
풀이 과정
1. 블록이 터지면 윗 블럭들의 행을 바꿔야하기 때문에 보드의 행과 열을 바꾸어 조작하기 쉽게 만든다.
기존 보드:
['A','B','C']
['A','A','D']
['A','A','E']
변환한 보드:
['A','A','A']
['B','A','A']
['C','D','E']
2. 같은 모양의 2x2 블록을 제거하고 제거된 블럭('0') 개수 반환
['A','0','0']
['B','0','0']
['C','D','E']
3. 제거된 블록 없애고 위에 있는 블록 땡기기
['펑','펑','A']
['펑','펑','B']
['C','D','E']
"""
answer = 0
reversed_board = list(map(list,zip(*board)))
while True:
pop = pop_block(reversed_board, m, n)
if pop == 0:
return answer
answer += pop
return answer배운 점
테트리스와 비슷한 보드판 문제는 2차원 배열에서 행과 열을 뒤집어서 조작하면 처리하기 쉽다는 것을 알게 되었다. 테트리스형 문제는 원소가 아래로 내려오는 형태이기 때문에 행을 바꿔주어야 하는데, 이 작업은 스택을 이용해 처리하면 간단해진다는 풀이를 떠올릴 수 있다.
스택을 이용하면 된다는 발상까지는 떠올렸지만 블럭이 사라졌을 때 인덱스를 조정하고, 블럭이 겹치는 경우의 처리를 어떻게 할 지는 생각해내기 어려웠다. 다른 사람들의 풀이를 참고하였는데 블럭이 겹치는 경우에는 인덱스 값을 집합으로 두고 합집합 연산을 하면 간단하게 처리할 수 있었다.
그리고 블럭이 사라졌을 때는 그 원소를 임의의 값(나의 경우 '0')으로 치환하고 '0'의 개수를 반환한 뒤, 다음 처리를 위해서 '펑'으로 변경한 리스트를 맨 앞에 넣어주고 아직 사라지지 않은 원소들을 그 뒤에 넣어주는 방식으로 풀이하였다.
어려웠지만 2차원 배열의 조작법과 치환을 이용한 처리라는 아이디어에 대해 배울 수 있어서 유익했다.
문제 설명
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 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 |
