[Python] SWEA 5656 벽돌깨기

SW Expert Academy

<Pass된 코드>

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
 
def deepcopy(lst):
    new_lst = []
    for y in range(len(lst)):
        temp = []
        for x in range(len(lst[y])):
            temp.append(lst[y][x])
        new_lst.append(temp)
    return new_lst
 
def erase_bricks(y, x, cur_bricks):
    Q = [(y, x, cur_bricks[y][x])]
    cur_bricks[y][x] = 0
 
    erased_bricks = 1
    while Q:
        cur_y, cur_x, cur_power = Q.pop(0)
 
        for p in range(1, cur_power):
            for d in range(4):
                new_y, new_x = cur_y + p * dy[d], cur_x + p * dx[d]
                if -1 < new_y < H and -1 < new_x < W and cur_bricks[new_y][new_x] != 0:
                    if cur_bricks[new_y][new_x] != 1:
                        Q.append((new_y, new_x, cur_bricks[new_y][new_x]))
                    erased_bricks += 1
                    cur_bricks[new_y][new_x] = 0
 
    return erased_bricks
 
def sort_bricks(cur_bricks):
    for x in range(W):
        cur_w_bricks = []
        for y in range(H - 1, -1, -1):
            if cur_bricks[y][x] != 0:
                cur_w_bricks.append(cur_bricks[y][x])
                cur_bricks[y][x] = 0
 
        for h in range(len(cur_w_bricks)):
             cur_bricks[H - 1 - h][x] = cur_w_bricks[h]
 
 
def dfs(result, k, bricks):
    global max_result
    if k == N:
        if max_result < result:
            max_result = result
        return
 
    for w in range(W):
        cur_bricks = deepcopy(bricks)
        cur_h = 0
 
        while cur_h < H and not cur_bricks[cur_h][w]:
            cur_h += 1
 
        num_erase = 0
        if cur_h < H:
            num_erase = erase_bricks(cur_h, w, cur_bricks)
            sort_bricks(cur_bricks)
        dfs(result + num_erase, k + 1, cur_bricks)
 
 
 
for tc in range(int(input())):
    N, W, H = map(int, input().split())
 
    origin_bricks = [list(map(int, input().split())) for _ in range(H)]
    num_all_bricks = 0
    for y in range(H):
        for x in range(W):
            if origin_bricks[y][x] != 0:
                num_all_bricks += 1
 
    max_result = 0
    dfs(0, 0, origin_bricks)
 
    print('#{} {}'.format(tc + 1, num_all_bricks - max_result))

상당히 길다..

 

<기본 아이디어>

• 탐색하기 전에 전체 벽돌 수를 세서 num_all_bricks에 저장해둔다.
• 구슬을 떨어뜨린 횟수 차와 위치에 대한 탐색은 DFS로 진행하고 떨어뜨린 구슬이 벽돌을 부수고 연쇄작용으로 부숴지는 탐색은 BFS를 진행하였다.
• dfs() 함수 안에 벽돌을 지우는 함수 erase_bricks()와 지워진 벽돌을 정돈하는 함수 sort_bricks()를 따로 만들어 분리하였다.
• 탐색을 마치고 돌아왔을 때 이미 벽돌이 지워진 게임판을 사용할 수는 없기 때문에 깊은 복사로 게임판을 복사하는 함수 deepcopy()를 만든다.

<고찰>

• 코드를 돌리니 754 ms의 실행시간으로 Pass되었다.
• 혹시 더 줄일 수 있는 방법이 없을까 고민해보았다.

<실행 시간 줄이기 대작전>

1. 벽돌 정렬하는 코드 방식 변경

<기존 코드>

def sort_bricks(cur_bricks):
    for x in range(W):
        cur_w_bricks = []
        for y in range(H - 1, -1, -1):
            if cur_bricks[y][x] != 0:
                cur_w_bricks.append(cur_bricks[y][x])
                cur_bricks[y][x] = 0
 
        for h in range(len(cur_w_bricks)):
             cur_bricks[H - 1 - h][x] = cur_w_bricks[h]

기존에는 y축 방향으로 쭉 벽돌을 훑으면서 벽돌을 모은 다음에 다시 차곡차곡 쌓는 방식

<새로운 코드>

def sort_bricks(cur_bricks):
    for x in range(W):
        prev = H - 1
        for y in range(H - 1, -1, -1):
            if cur_bricks[y][x]:
                if prev != y:
                    cur_bricks[prev][x], cur_bricks[y][x] = cur_bricks[y][x], cur_bricks[prev][x]
                prev -= 1

새로운 방식은 y축 방향으로 처음부터 훑으면서 벽돌을 만날때마다 벽돌을 쌓아야할 위치를 바꿔주는 방식

 

2. deepcopy 하는 방식 변경

def deepcopy(lst):
    new_lst = []
    for y in range(len(lst)):
        temp = []
        for x in range(len(lst[y])):
            temp.append(lst[y][x])
        new_lst.append(temp)
    return new_lst
...
# cur_bricks = deepcopy(bricks)
cur_bricks = [b[:] for b in bricks]
...

원래는 이차원 행렬을 깊은 복사 하는 deepcopy()라는 함수를 따로 만들어 사용했으나 리스트 슬라이싱을 사용하는 깊은 복사로 변경하였다.

 

파이썬에서 deepcopy를 하는 방법에 따른 실행 속도에 관련된 내용은 다음 글에 잘 나와있었다.

파이썬 (Python) - 깊은 복사 (Deep Copy)