문제
접근
크게 두단계로 이루어져 있다.
- 2x2 블록 찾기
n x m 블록을 하나씩 검사하며 인접한 4개 블록이 같은지 검사한다.
왼쪽 상단부터 검사를 시작하며 검사하는 블록 기준으로 오른쪽, 아래, 오른쪽 아래의 블록이 같은지 체크한다.
이렇게 검사하면 중복된 곳은 검사하지 않는다.
같다면 해당 블록의 숫자를 카운팅해준다.
문제는 예제처럼 블록이 겹쳐있는 부분이다.
이 경우에 중복 카운팅을 막기 위해서 checkboard를 두어 같은 곳은 체크를 하며 진행한다.
checkboard는 다음 단계를 진행할 때 유용하게 쓰이기 때문에, 없어지는 블록들의 위치를 잘 표시해준다.
- board 움직이기
checkboard를 아래에서 부터 확인하며 비어있는 블록을 발견하면 위의 블록과 자리를 바꿔준다.
이 때 한칸 위도 빈블록일 수도 있으므로, 해당 라인에서 채워져있는 블록을 만날 때까지 탐색한다.
코드
- 파이썬 코드
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
def solution(m, n, board):
answer = 0
checkBoard = [[1 for _ in range(n)] for _ in range(m)]
while True:
flag = True
for i in range(m-1):
for j in range(n-1):
if board[i][j] == 'x':
continue
if board[i][j] == board[i][j+1] == board[i+1][j+1] == board[i+1][j] :
if checkBoard[i][j] != 0:
flag = False
if checkBoard[i][j]:
answer += 1
checkBoard[i][j] = 0
if checkBoard[i][j+1]:
answer += 1
checkBoard[i][j+1] = 0
if checkBoard[i+1][j]:
answer += 1
checkBoard[i+1][j] = 0
if checkBoard[i+1][j+1]:
answer += 1
checkBoard[i+1][j+1] = 0
for j in range(n):
for i in range(m):
if checkBoard[m-i-1][j] == 0:
t = m-i-1
while True:
t -= 1
if t < 0:
board[m-i-1] = board[m-i-1][:j] + 'x' + board[m-i-1][j+1:]
break
if checkBoard[t][j] == 1:
checkBoard[m-i-1][j], checkBoard[t][j] = checkBoard[t][j], checkBoard[m-i-1][j]
board[m-i-1] = board[m-i-1][:j] + board[t][j] + board[m-i-1][j+1:]
board[t] = board[t][:j] + 'x' + board[t][j+1:]
break
if flag:
break
return answer