SWEA [모의 SW 역량테스트] 벽돌 깨기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE

SW Expert Academy

 

내 풀이:

import itertools
 
def go(j):
    for i in range(H):
        if new[i][j] != 0:
            bomb(i, j)
            break
 
 
def bomb(y, x):
    global H, W
    val = new[y][x]
    new[y][x] = 0
 
    for len in range(1, val):
        for dir in range(4):
            ny = y + len * dy[dir]
            nx = x + len * dx[dir]
 
            if 0 <= ny <= H-1 and 0 <= nx <= W-1 and new[ny][nx] != 0:
                bomb(ny, nx)
 
 
def gravity():
    for j in range(W):
        i = H-1
        while new[i][j] != 0 and i >= 0:
            i -= 1
 
        save = i
        i -= 1
 
        while i >= 0:
            if new[i][j] != 0:
                new[save][j] = new[i][j]
                new[i][j] = 0
                save -= 1
            i -= 1
 
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
 
T = int(input())
for case in range(1, T+1):
    N, W, H = map(int,input().split())
    arr = [list(map(int,input().split())) for _ in range(H)]
    lst = list(itertools.product([i for i in range(W)], repeat = N))
    ans = 180
 
    for a in lst:
        new = [arr[_][:] for _ in range(H)]
 
        for b in a:
            go(b)
            gravity()
 
        res = 0
        for i in range(H):
            for j in range(W):
                if new[i][j] != 0:
                    res += 1
 
        ans = min(ans, res)
 
        if ans == 0:
            break
 
    print("#%d"%(case), ans)

Python3, 1078ms

코딩할 때 module 사용을 지양해왔는데 이번 문제를 풀 때는 itertools의 product를 사용해보았다. 문제를 풀 때 구슬을 떨어뜨릴 열을 선택하는 부분은 모두 탐색해주어야 한다고 판단하여 product로 리스트를 모두 뽑아 함수를 돌렸다. 베타 처리 방식을 모르는 상태에서 이 문제를 처음 접했을 때 문제 접근 방향을 찾기 어려워했으며 코딩도 엄청 지저분하게 작성되어 마음에 안 들었는데 이번에 문제를 생각보다 깔끔하게 풀어서 나름 만족한 문제이다.