[삼성sw 5656] 벽돌깨기(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

중복조합에 대해 공부할 수 있게 된 문제.

처음 이 문제를 보자마자

백트레킹이 생각났습니다.

벽돌을 0~w까지 던지니깐

이걸 N개만큼 반복하면 되겠네.

그런데 N의 숫자가 커지면 커질수록

시간초과 이슈를 벗어나긴 힘들어보였습니다.

(무엇보다 계속 deepcopy를 해줘야하는데

이게 시간 은근 많이 잡아먹음)

 

그래서 힌트를 얻어, 중복조합으로 벽돌을 내리는 모든 경우를 다 구하고

그 때 벽돌이 어떻게 되는지 구했습니다.

 

까다로웠던 점은

'2이상의 숫자를 만나면

그 만큼 벽돌을 더 꺠줘야한다'라는 점.

이 부분은 bfs처럼 구현해줬습니다.

벽돌의 숫자만큼 가로,세로를 구한 다음에

깬 벽돌의 좌표와 숫자를 queue에 넣어줍니다.

만약 해당 숫자가 1이라면 

굳이 할 필요없으니 넘겨버리고요.

 

추가로 이 문제에서 주의할 점은

'모든 벽돌을 다 깨는 케이스가 나온다면

다른 케이스를 살펴볼 이유가 없다'는 것.

이걸 구현하지 않으면

예제5를 돌릴 때

사실상 무한루프를 도는 것처럼

시간이 엄청나게 걸리는 걸 볼 수 있습니다.

그런데, 이미 벽돌을 다 꺠는 케이스가 나오는데

굳이 더 할 필요가 없잖아요?

이 부분을 구현해주니

예제5도 시간정복이 되었습니다.

from copy import deepcopy
from itertools import product
from collections import deque
T=int(input())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def inside(x,y):
    if x<0 or x>=H or y<0 or y>=W:
        return False
    return True

def bomb(sx,sy):
    q=deque()
    q.append((sx,sy,new[sx][sy]))
    blu=set()
    blu.add((sx,sy))

    while q:
        x,y,cnt=q.popleft()
        if cnt==1:
            continue
        for g in range(cnt-1,0,-1):
            for d in range(4):
                nx=x+dx[d]*g
                ny=y+dy[d]*g

                if inside(nx,ny):
                    if not (nx,ny) in blu and new[nx][ny]>0:
                        blu.add((nx,ny))
                        q.append((nx,ny,new[nx][ny]))


    for px,py in blu:
        new[px][py]=0


for t in range(1,T+1):
    N,W,H=map(int,input().split())
    room=[list(map(int,input().split())) for _ in range(H)]
    p=[i for i in range(W)]
    answer=W*H
    #1중복순열로 벽돌의 위치를 각각 다 구한다
    for case in list(product(p,repeat=N)):
        new=deepcopy(room)
        #print(case)
        #2 벽돌 각각을 던진다

        for by in case:
            #맨아래에 0만 있다면 더이상 블록이 없다는 의미이므로 정지
            if new[H-1].count(0)==W:
                break
            flag=False
            for bx in range(H):
                if new[bx][by]>0:
                    bomb(bx,by)
                    flag=True
                    break

            if not flag:
                continue

            #3. 떨어뜨린 블록이 있다면, 아래로 내려준다
            for y in range(W):
                fall_p=0
                for x in range(H-1,-1,-1):
                    if new[x][y]==0:
                        fall_p+=1

                    elif new[x][y]>0:
                        new[x][y],new[x+fall_p][y]=new[x+fall_p][y],new[x][y]
            # if case==(2,2,6):
            #     for x in range(H):
            #         print(new[x])
            #     print()

        zeros=0
        for h in range(H):
            zeros+=new[h].count(0)

        point=W*H-zeros

        if point<answer:
            answer=point
            # print(point,case)
        #어떤 케이스든, 벽돌을 다 깨는 경우가 있다면, 굳이 다른 케이스를 더 볼 이유가 없다.
        if answer==0:
            break
    print("#%d %d"%(t,answer))

 

백트레킹도 좋지만

중복조합으로 해결할 수 있는 좋은 문제.

중복조합을 활용해서 좋은 공부가 되었습니다.