[프로그래머스] 프렌즈4블록

 

📌문제

https://school.programmers.co.kr/learn/courses/30/lessons/17679?language=python3

 

🎖️난이도

Level 2

 

✔️풀이

from collections import deque

def check2x2(i, j, m, n, board):
    if i+1 in range(0, m) and j+1 in range(0, n):
        if board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1]:
            return True
    return False

def replaceTo0(board, visited):
    for x, y in visited:
        board[x][y] = 0

def pop_board(m, n, board):
    for j in range(n):
        tmp_list = [board[k][j] for k in range(m) if board[k][j] != 0]
        zero_cnt = m - len(tmp_list)
        for i in range(m):
            board[i][j] = 0 if i < zero_cnt else tmp_list[i-zero_cnt]
            
        #board[:][j] = [0] * board[:][j].count(0) + tmp_list # 틀린 방법!
        
def pop2x2(m, n, board):
    dx = [0, 1, 1]
    dy = [1, 0, 1]
    
    pop_num = 0
    
    for i in range(m):
        for j in range(n):
            if board[i][j] == 0:
                continue
            if check2x2(i, j, m, n, board):
                # bfs
                queue = deque()
                queue.append([i, j])
                visited = set()
                visited.add((i, j))
                
                while queue:
                    x, y = queue.popleft()
                    for k in range(3):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx in range(0, m) and ny in range(0, n):
                            if (nx, ny) not in visited:
                                visited.add((nx, ny))
                                if check2x2(nx, ny, m, n, board):
                                    queue.append([nx, ny])
                pop_num += len(visited)
                
                replaceTo0(board, visited)
                
    pop_board(m, n, board) # 한 step에서 여러 군데 한번에 모아서 pop 해야됨!!
                
    return pop_num


def solution(m, n, board):
    # replace str to arr
    board = list(map(list, board))
    
    cnt = 0   
    while True:
        tmp_cnt = pop2x2(m, n, board)
        
        if tmp_cnt == 0:
            break
        cnt += tmp_cnt
    
    return cnt

 

🧠노트

BFS + 빡구현..!

 

전체적으로 구현이 어려웠는데,

pop_board 함수 구현 아이디어를 생각해 내는 것이 어려웠다. 

(각 step에서 pop할 애들 모두 0으로 바꿔주고 아래로 내려주는 작업)

 

최종적으로 0으로 표시된(터트릴) 애들을 쭉쭉 아래로 당기고, 윗쪽 빈 칸은 다시 0으로 채우는 과정에서 

2차원 배열을 행 단위로 생각하는 게 아니라,

1차원 배열인 열 단위로 생각해서 0이 아닌 애들부터 아래로 차곡차곡 쌓고, 나머지 윗부분은 0으로 갈아끼워주면 된다!

 

이때,

열 단위로 아예 갈아끼우려고 슬라이싱을 이용했더니 안되어서 (board[:][j])

0 개수를 미리 계산해서(zero_cnt) 위에서부터 0부터 넣고 그 다음에 0이 아닌 애들로 넣어줬다.

def pop_board(m, n, board):
    for j in range(n):
        tmp_list = [board[k][j] for k in range(m) if board[k][j] != 0] # 0이 아닌 애들 따로 누적
        zero_cnt = m - len(tmp_list)
        for i in range(m):
            board[i][j] = 0 if i < zero_cnt else tmp_list[i-zero_cnt] # 0부터 위에 채우기

 

또한,

이 pop_board 함수를 호출하는 시기도 이 문제의 key point! 

 

한 step에서 모든 local 부위에서 pop할 수 있는 부분 모두 0으로 다 바꿔주고 난 후에

맨 마지막 단계에서 pop해서 내려줘야 한다. (새로운 board 갱신)

즉 while 돌 때마다, pop2x2 함수의 끝에서 호출해야 함!

(각 local 부위마다 호출하면 test case 10번에서 오류남)

 

🔍참고

[ 2차원 배열의 열(col) 추출하기 ]

슬라이싱으로는 2차원 배열의 열(세로) 추출 안됨! 

단, Numpy로는 가능~!

 

 

1. 2중 for문으로 접근

arr = [
    [1, 2],
    [3, 4],
    [5, 6],
    [7, 8]
]

for i in range(len(arr[0])):
    for row in arr:
        print(row[i], end = ' ')
    print()

# 1 3 5 7
# 2 4 6 8

print([row[0] for row in arr])
# [1, 3, 5, 7]

# 열 추출 이렇게 하면 틀림!

print(arr[:][0]) # 모든 행을 다 가져오고([:]), 그 중에서 0번째 항목(행)을 가져와라!
# [1, 2]

 

 

2. Numpy로 슬라이싱

 

단, 코테에서 numpy는 안되는 경우들이 있으므로 1번 방법처럼 for문을 이용하자!