[swea 5656] 벽돌깨기

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo

SW Expert Academy

2. 접근 방법

1. 만약 board에 벽돌이 하나도 존재하지 않는다면 -> 0 출력, 로직 끝

2. 만약 N개의 구슬을 떨어뜨렸다면 -> 현재 가장 적은 벽돌 갯수 출력, 로직 끝

3. 아직 N개까지 구슬을 안떨어뜨렸다면 -> 구슬 떨어뜨리기 고고

 

구슬 떨어뜨리기(DFS)

1. 1~W열 중 하나를 고른다.

2. 해당 열에서 가장 위에 있는 벽돌에 구슬이 떨어짐

3. 구슬이 떨어지면서 연쇄 반응이 한 번에 일어남 (BFS)

4. 연쇄 반응 후 사라진 벽돌들은 치우고, 그 자리에 위에 있던 벽돌들 내려줌 (중력에 의해)

5. 구슬 떨어뜨리기 고고

3. 코드

python

from collections import deque

def isBoard(x, y):
    if 0 <= x < W and 0 <= y < H:
        return True
    return False


def downBoard(cnt):
    for x in range(W):
        temp_row = []
        for y in range(H - 1, -1, -1):
            if board[y][x] > 0:
                temp_row.append(board[y][x])
        for y in range(H - 1, -1, -1):
            if temp_row:
                val = temp_row.pop(0)
                board[y][x] = val
            else:
                board[y][x] = 0
    solve(cnt + 1)

def bomb(x, y, cnt):
    q = deque()
    q.append((x, y))
    dir = ((0, 1), (1, 0), (0, -1), (-1, 0))

    visited = [[False] * W for _ in range(H)]
    visited[y][x] = True
    while q:
        nx, ny = q.popleft()
        size = board[ny][nx]
        board[ny][nx] = 0

        if size > 0:
            for i in range(1, size):
                for j in range(4):
                    tx, ty = nx + dir[j][0] * i, ny + dir[j][1] * i
                    if isBoard(tx, ty) and not visited[ty][tx] and board[ty][tx] != 0:
                        visited[ty][tx] = True
                        q.append((tx, ty))
    downBoard(cnt)

def findBomb(x, cnt):
    global board
    y = 0
    while y < H and board[y][x] == 0:
        y += 1
    if y <= H - 1:
        temp_board = [board[i][:] for i in range(len(board))]
        bomb(x, y, cnt)
        board = [temp_board[i][:] for i in range(len(temp_board))]
    return

def countBomb():
    cnt = 0
    for y in range(H):
        for x in range(W):
            if board[y][x] > 0:
                cnt += 1
    return cnt

def solve(cnt):
    global minAns

    count_bomb = countBomb()

    if count_bomb == 0:
        minAns = 0
        return

    if cnt == N:
        minAns = min(minAns, count_bomb)
        return

    for i in range(W):
        findBomb(i, cnt)

T = int(input())
for tc in range(1, T + 1):
    N, W, H = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(H)]
    minAns = W * H

    solve(0)
    print('#{} {}'.format(tc, minAns))

4. 마치며

문제에서 하란대로 하면 되긴 하는데

디버깅 하는 과정에서 중간에 등호 하나 빠뜨린 거 찾느라 힘드렁ㅆ음 ㅠ