[프로그래머스] [1차] 프렌즈4블록 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 먼저 제거될 수 있는 블록의 위치와 개수를 파악하고 해당 위치의 블록을 제거한다.
이후 제거된 블록의 자리를 위의 블록이 내려와 채우게 된다.
블록이 채워질 때는 아래에서부터 빈자리를 파악하여 블록을 채워주면 된다.
 

1. deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 블록의 위치를 저장해 줄 그래프를 생성하고 graph = list()
3. for _ in range(m): graph.append([0] * n)
4. 초기 블록 위치를 저장한다. for i in range(len(board)): for j in range(len(board[i])): graph[i][j] = board[i][j]
5. 원하는 시점에서 종료하기 위해 무한 반복문을 사용한다. while (True)
6. 블록을 제거할 수 있는 조건은 같은 그림의 2x2 블록이 존재해야 한다. 해당 조건을 확인할 때 사용하기 위해 추가로 3가지 방향을 저장해 둔다. check = [[1, 0], [0, 1], [1, 1]]
7. 제거할 블록의 위치를 저장할 리스트를 생성한다. re = list()
8. 처음부터 끝까지 반복하며 for i in range(m): for j in range(n)
9. 만약 해당 위치가 공백이 아닐 경우 if (graph[i][j] != 0)
10. 해당 위치의 그림을 기억한다. shape = graph[i][j]
11. 처음 블록의 위치를 저장한다. li = [[i, j]]
12. 나머지 3방향의 블록을 확인하며 for k in check
13. 만약 다음 블록의 위치가 존재한다면  if (0 <= i + k[0] < m) and (0 <= j + k[1] < n)
14. 다음 블록의 그림이 현재 그림과 일치하는지 확인한다. if (graph[i + k[0]][j + k[1]] == shape)
15. 그림이 동일하다면 해당 블록의 위치를 저장한다. li.append([i + k[0], j + k[1]])
16. 나머지 3방향을 모두 확인한 후, 만약 일치하는 그림이 4개 이상이면 if (len(li) >= 4)
17. 해당 블록의 위치를 하나씩 불러와 for k in li
18. 제거할 블록의 위치 리스트에 중복되지 않도록 추가한다. if (k not in re): re.append(k)
19. 추가된 위치 개수만큼 제거할 블록의 개수도 증가시킨다. answer += 1
20. 만약 제거할 블록의 개수가 0개이면 더 이상 제거할 블록이 없으므로 종료한다. if (len(re) == 0): break
21. 제거할 블록이 있다면 해당 위치를 하나씩 불러와 해당 블록을 제거해 준다. for i in re: graph[i[0]][i[1]] = 0
22. 제거 후, 블록은 각 열별로 아래로 내려오므로 블록이 제거되는 열을 따로 저장한다. col = set(i[1] for i in re)
23. 따로 지정한 열을 하나씩 불러와 for i in col
24. 해당 열의 블록을 deque 자료구조로 저장한다. queue = deque(graph[j][i] for j in range(m))
25. 블록이 모두 아래로 내려왔는지 확인할 변수를 생성한다. finish = False
26. 블록이 내려오면 아래에서부터 채워지므로 아래에서부터 블록을 채운다. for j in range(m - 1, -1, -1)
27. 만약 해당 위치가 빈 공간이면 반복한다. while (queue[j] == 0)
28. 만약 해당 위치에서부터 위의 공간이 모두 빈 공간이면 if (list(queue)[ : j + 1].count(0) == len(list(queue)[ : j + 1]))
29. 블록을 모두 내린 후이므로 종료한다. finish = True  break
30. 내릴 블록이 남아있다면 채울 공간을 저장하고 temp = queue[j]
31. 해당 공간을 제거한 뒤 del queue[j]
32. 저장한 공간을 제일 앞으로 옮긴다. queue.appendleft(temp)
33. 블록을 모두 내렸다면 종료한다. if (finish): break
34. 모두 내린 블록의 새 위치를 하나씩 불러와 for j in range(len(queue))
35. 다음 블록 제거를 위해 그래프에 새로 저장한다. graph[j][i] = queue.popleft()

반응형

3. 소스코드

from collections import deque

def solution(m, n, board):
    answer = 0
    
    graph = list()
    for _ in range(m):
        graph.append([0] * n)

    for i in range(len(board)):
        for j in range(len(board[i])):
            graph[i][j] = board[i][j]

    while (True):
        check = [[1, 0], [0, 1], [1, 1]]
        re = list()
        for i in range(m):
            for j in range(n):
                if (graph[i][j] != 0):
                    shape = graph[i][j]
                    li = [[i, j]]
                    for k in check:
                        if (0 <= i + k[0] < m) and (0 <= j + k[1] < n):
                            if (graph[i + k[0]][j + k[1]] == shape):
                                li.append([i + k[0], j + k[1]])
    
                    if (len(li) >= 4):
                        for k in li:
                            if (k not in re):
                                re.append(k)
                                answer += 1
        
        if (len(re) == 0):
            break
        
        for i in re:
            graph[i[0]][i[1]] = 0
        
        col = set(i[1] for i in re)
        for i in col:
            queue = deque(graph[j][i] for j in range(m))

            finish = False
            for j in range(m - 1, -1, -1):
                while (queue[j] == 0):
                    if (list(queue)[ : j + 1].count(0) == len(list(queue)[ : j + 1])):
                        finish = True
                        break
                    temp = queue[j]
                    del queue[j]
                    queue.appendleft(temp)

                if (finish):
                    break

            for j in range(len(queue)):
                graph[j][i] = queue.popleft()

    return answer