문제 링크

이 문제를 푸는데 1시간 반이나 걸렸지만 한 큐에 통과했다!!😭🎉
이 문제는구현문제며 2x2를 터트리는 기능과 터트려진 block에 위에서부터 끌어오는 기능으로 접근하였다.

🍀 2x2 블록 터트리기

터트린 것: ''(빈 문자열)로 표시

1. 2x2 블록이므로 row -> m - 1, col -> n - 1까지 탐색.
   1. board[row][col]에 값이 있을 경우에만 오른쪽, 우측 하단 대각선, 아래를 탐색하면서 값이 같은 경우 count += 1을 한다.
   2. 2x2안의 값이 모두 동일하다면 count == 4이고 이 때 위치의 정보들을 set에 넣어준다.
   3. 탐색이 다 끝나면 위치 정보들을 기반으로 ''빈문자열로 값을 대체한다.
   4. 터진 블록의 개수, 터트린 블록을 반영한 board를 return한다.

과정 1-2에서 set을 쓴 이유는 아래와 같다.

set에 넣어준 이유는 탐색하면서 빈 배열로 만들어 블록을 터트릴 수 있지만 board[row][col] = ''이 되면 탐색을 제대로 하지 못하기 때문이다.`문제 설명에 라이온이 겹치는 경우

code

def pang_blocks(m, n, board):
    removed_block_set = set()
    dxs = [0, 1, 1]
    dys = [1, 1, 0]
    
    for row in range(m - 1):
        for col in range(n - 1):
            if board[row][col] != '':
                count = 1
                
                for dx, dy in zip(dxs, dys):
                    next_x, next_y = row + dx, col + dy
                    if board[row][col] == board[next_x][next_y]:
                        count += 1
    
                if count == 4:  
                    removed_block_set.add((row, col))
                    removed_block_set.update([(row + dx, col + dy) for dx, dy in zip(dxs, dys)])
                
    # fill with empty string where the block removed!
    for row, col in removed_block_set:
        board[row][col] = ''
        
    
    return len(removed_block_set), board

🍀 빈 블록까지 값 떨어뜨리기

이 부분에서 많은 시간이 걸렸는데 결국은 해결했다!!!
아래에 대략적인 로직만 적어놓고 이는 글보단 그림을 첨부하면 좋을 것 같아서 이해를 도와줄 수 있는 그림을 로직 아래 첨부했다.

1. 각 열에 대해 행을 돌면서 위에서부터 아래로 탐색
   1. 빈 문자열을 찾을 시
      1. 빈 문자열의 바로 위부터 row -> 0까지 위치를 한칸씩 끌어내리면서 ''빈 문자열로 대체
   2. 빈 문자열을 찾지 못하면 아래로 계속 탐색

code

def drop_blocks(m, n, board):
    for col in range(n):
        for row in range(m):
            if board[row][col] == '':
                for prev_row in range(row - 1, -1, -1):
                    board[prev_row + 1][col] = board[prev_row][col]
                    board[prev_row][col] = ''

                    
    return board

✅ 전체 코드

import copy

def pang_blocks(m, n, board):
    removed_block_set = set()
    dxs = [0, 1, 1]
    dys = [1, 1, 0]
    
    for row in range(m - 1):
        for col in range(n - 1):
            if board[row][col] != '':
                count = 1
                
                for dx, dy in zip(dxs, dys):
                    next_x, next_y = row + dx, col + dy
                    if board[row][col] == board[next_x][next_y]:
                        count += 1
    
                if count == 4:  
                    removed_block_set.add((row, col))
                    removed_block_set.update([(row + dx, col + dy) for dx, dy in zip(dxs, dys)])
                
    # fill with empty string where the block removed!
    for row, col in removed_block_set:
        board[row][col] = ''
        
    
    return len(removed_block_set), board

def drop_blocks(m, n, board):
    for col in range(n):
        for row in range(m):
            if board[row][col] == '':
                for prev_row in range(row - 1, -1, -1):
                    board[prev_row + 1][col] = board[prev_row][col]
                    board[prev_row][col] = ''

                    
    return board

def solution(m, n, board):
    answer = 0
    copy_board = copy.deepcopy(list(map(list, board)))
    
    while True:
        count_removed_blocks, next_board = pang_blocks(m, n, copy_board)
        if count_removed_blocks == 0:
            break
        answer += count_removed_blocks
        dropped_board = drop_blocks(m, n, next_board)

    
    return answer

📒 다른사람 풀이1

이 풀이를 봤을 때 위의 값을 아래로 끌어오는 것이 직관적으로 눈에 잘 들어왔다.

1. 전체를 돌면서 위 아래 대각선이 같은걸 찾는다.
2. 찾은 위치를 1로 바꾼다.
3. 1의 갯수를 센다.
4. 맨 밑 부터 탐색하며 만약 1이면 위에를 내려준다.
5. while을 사용하여 1이 아닐때 까지 감소시키고
6. 바꿔준다.

def solution(m, n, board):
    answer = 0
    board = list(map(list, board))

    while True:
        visited = [[0] * n for _ in range(m)]
        for i in range(m - 1):
            for j in range(n - 1):
                k = board[i][j]
                if k != 0:
                    if board[i][j + 1] == k and board[i + 1][j] == k and board[i + 1][j + 1] == k:
                        visited[i][j], visited[i + 1][j], visited[i][j + 1], visited[i + 1][j + 1] = 1, 1, 1, 1

        cnt = 0
        for i in range(m):
            cnt += sum(visited[i])
        if not cnt:
            break
        answer += cnt
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if visited[i][j]:
                    x = i - 1
                    while x >= 0 and visited[x][j] == 1:
                        x -= 1
                    if x < 0:
                        board[i][j] = 0
                    else:
                        board[i][j] = board[x][j]
                        visited[x][j] = 1

    return answer

출처

📒 다른사람 풀이2

이 풀이는 board를 재배열하는 것만 가져온 것으로 프로그래머스에서 통과한 사람들만 볼 수 있는 다른 사람풀이에서 가져왔다.
개인적으로 되게 신박해서 감탄했다. 문자열로 처리를 했으며 블록이 터진 곳을 '0'으로 처리하고 '0'의 공간을 없앤뒤에 row의 윗부분부터 zfill로 0으로 채움으로써 위의 블록을 빈 블록까지 끌어내렸다.

def restruct(m, n, board):
    re_board = [''] * m
    for col in range(n):
        ys = ''.join([board[row][col] for row in range(m)]).replace('0','').zfill(m)
        for row in range(m):
            re_board[row] += ys[row]

    return re_board

🤔 회고

다른사람 풀이를 보고 느낀 것이 많다.
첫 번째로는 난 set을 이용하여 위치정보를 count한 것을 answer에 더했는데 다른사람풀이에서는 visited(방문 보다는 터진 위치이므로 mark_empty_block이 더 나을 것 같다)를 이용해서 터진 위치를 1로 체크하고 1의 개수를 새서 answer에 더했다.
두 번째는 아예 문자열과 replace, zfill을 이용하여 옮기는 효과를 구현해낸 것에 감탄했다.
블로깅을 시작한지 얼마 안 됐지만, 처음에 프로그래머스에서 코딩 연습문제를 풀이하면서 다른 사람 코드들은 거의 안 봤는데 요새 보면서 많은 것을 느낀다. 더 많이 참고하고 배울 점을 찾아나가야겠다.