2024년 2월 27일 알고리즘 문제풀이
문제
난이도
Lv.2
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def solution(m, n, board):
answer = 0
# 시계방향으로 90도 회전하는 함수
# 따라서 n x m 인 배열이 된다.
# 블록의 추락도 아래가 아닌 왼쪽으로 발생해야 한다.
arr = [[] for _ in range(n)]
for k in range(n):
for i in range(m-1,-1,-1):
arr[k].append(board[i][k])
# 점을 기준으로 오른쪽, 아래, 오른쪽 아래가 모두 동일한지 확인하는 함수
def check(a,b):
result = False
tmp = arr[a][b]
if arr[a+1][b] == tmp and arr[a][b+1] == tmp and arr[a+1][b+1] == tmp:
result = True
return result
# 점을 기준으로 오른쪽, 아래, 오른쪽 아래 4개를 지우는 함수.
# 지워지는 블록이 다른 곳과 겹칠 경우를 대비하여, 실제 지워진 갯수를 계산하여 반환
def delete(a,b):
result = 0
if arr[a][b] != '0':
arr[a][b] = '0'
result += 1
if arr[a+1][b] != '0':
arr[a+1][b] = '0'
result += 1
if arr[a][b+1] != '0':
arr[a][b+1] = '0'
result += 1
if arr[a+1][b+1] != '0':
arr[a+1][b+1] = '0'
result += 1
return result
# 90도 회전하였기 때문에, 왼쪽으로 블록이 떨어지는 함수 구현
# 각 행마다, 비어있는 열을 발견할 경우 오른쪽을 탐색하여 떨어질 블록을 찾아 바꿔준다.
# 한 칸씩 떨어뜨리면, 여러 블록을 떨어뜨리는 경우가 복잡해진다.
def fall():
for i in range(n):
for j in range(m):
if arr[i][j] == '0':
for k in range(j+1,m):
if arr[i][k] != '0':
arr[i][j] = arr[i][k]
arr[i][k] = '0'
break
# '0'이 아니라는 조건을 추가하지 않으면 무한루프가 실행된다.
while True:
delete_list = []
for i in range(n-1):
# 여기가 1,m 이면 테스트 5가 실패함
for j in range(m-1):
if arr[i][j] != '0' and check(i,j):
delete_list.append([i,j])
if not delete_list:
break
for a,b in delete_list:
tmp = delete(a,b)
answer += tmp
fall()
return answer
겁나 힘들게 풀었다… 기존에는 위와 같이 풀되, 90도로 회전하지 않았다. 이떄 발생하는 어려움은 블록을 부수고 떨어뜨리는 것을 구현하기 힘들었다. 위에서 아래로 떨어뜨릴 경우 같은 열이지만 다른 행인 원소들간의 비교가 이루어져야 한다. 위 각주에서도 말했지만 한 칸씩 옮길 경우 2개가 같이 떨어질 떄나, 여러 칸을 떨어뜨리는 경우의 수는 상당히 복잡하기 때문에 구현이 힘들었다. 추락을 같은 List 안에서 발생하도록 하면 훨씬 편해질 것이라고 생각해서 배열을 90도 회전하였다.
마지막에 테스트 5만 자꾸 실패하는 경우가 발생해서 예외를 찾기 힘들었는데, 추락을 구현하는 범위가 문제였다. 내가 구현한 추락은 현재 칸이 빈칸이면 이곳에 떨어질 블록이 있는지 확인하는 로직이기 떄문에 가장 아래칸부터 시작해야 한다. 하지만 범위는 두번째 칸부터 설정했는데, 범위를 설정할 떄는 떨어질 것은 두번째 것부터 있다고 생각했기 떄문이다.. 이 부분을 고치니 해결되었다.
