개발/algorithm
[프로그래머스][level2] [1차] 프렌즈4블록 - python
zzi_on2
2022. 4. 14. 22:30
문제 링크
https://programmers.co.kr/learn/courses/30/lessons/17679
코딩테스트 연습 - [1차] 프렌즈4블록
프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙
programmers.co.kr
풀이
1. 행과 열 뒤집기
2. 제거된 블록의 개수 세어주기
- 이전에 블록들이 제거돼서 블록이 없는 부분은 -1로 표시하고, 현 시점에 제거 될 수 있는 블록은 0 으로 표시
1) 그래프를 확인하면서 4개의 블록으로 묶여서 사라질 수 있으면 0으로 표시
2) 0의 개수를 세어서 제거될 블록의 개수 계산
3) 제거된 블록의 수 만큼 -1로 채우고, 아직 제거안된 블록들로 채우기
4) 갱신된 그래프과 제거된 0의 개수 리턴
3. 제거된 블록의 개수가 0이라면 더이상 제거될 블록이 없다는 것이므로 정답 리턴
제거된 블록이 있다면 블록 수 더하기
import copy
def remove(graph, m, n):
# 제거된 블록개수
pops = 0
# 제거된 블록 수 체크할 배열
tmp = copy.deepcopy(graph)
for i in range(1,n):
for j in range(1,m):
# 블록이 없는 곳이면 넘어가기
if graph[i][j] == -1:
continue
# 사라질 수 있으면
if graph[i][j] == graph[i-1][j] == graph[i][j-1] == graph[i-1][j-1]:
# 0으로 채워넣기
tmp[i][j], tmp[i-1][j], tmp[i][j-1], tmp[i-1][j-1] = 0,0,0,0
for i, v in enumerate(tmp):
# 0 의 개수세기
cnt = v.count(0)
pops += cnt
# 위에 있던 블록들 떨어뜨려주기
tmp[i] = [-1] * cnt + [ a for a in v if a!= 0]
return tmp, pops
def solution(m, n, board):
answer = 0
# 행과 열 뒤집기
graph = list(map(list, zip(*board)))
while True:
graph, pops = remove(graph,m,n)
# 더이상 제거될 블록이 없으면
if pops == 0 :
return answer
# 제거된 블록 수 더하기
answer += pops