[알고리즘] 백준16918 봄버맨 - 파이썬

https://www.acmicpc.net/problem/16918

16918번: 봄버맨

 

 

[정리안 된 풀이 코드]

# 16918 봄버맨
from collections import deque
from sys import stdin
input = stdin.readline
r, c, n = map(int, input().split())

graph = []
for _ in range(r):
    graph.append(list(input().strip()))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs(queue):
    while queue:
        y, x = queue.popleft()
        graph[y][x] = '.'
        for l in range(4):
            yy = dy[l] + y
            xx = dx[l] + x
            if 0 <= xx < c and 0 <= yy < r and graph[yy][xx] == 'O':
                graph[yy][xx] = '.'
                # queue.append((yy, xx)) 연쇄반응이 없다.

def search(q): # 폭탄의 위치 큐에 추가
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'O':
                q.append((i, j))

def result(graph): # 그래프 출력하는 함수
    for g in graph:
        print(*g, sep='')


queue = deque()
if n == 1:
    result(graph)
else:
    search(queue) # for문 돌기전에 폭탄의 위치를 큐에 저장
    for k in range(1,n):
        if (k+1) % 2 == 0: # for문돌면서 . -> O으로 바꿔야함
            for i in range(r):
                for j in range(c):
                    if graph[i][j] == '.':
                        graph[i][j] = 'O'
            if (k+1) == n: # 결과출력
                result(graph)
        else:
            bfs(queue)
            search(queue)
            if (k+1) == n: # 결과출력
                result(graph)

• 정리가 안된 코드.. 일단 풀이는 초마다 구분해서 문제에서 요구하는 처리를 해주면 된다. 짝수 초는 모든 비어있는 구간에 폭탄을 설치해야 한다는 점, 홀수 초는 1초를 제외하고 탐색을 통해 폭탄이 터질 시 정해진 범위 내를 '.'으로 바꿔줘야 한다.
• bfs에 주석처리 한부분을 보면 문제 지문에 연쇄반응은 없다고 나와있어서 꼭 지워줘야 한다.
• 이 코드는 내가 봐도 좀 지저분? 한 느낌이다. 너무 하드코딩되어있는데 1초면 그냥 출력, 1초가 넘어가면 for문을 돌면서 짝수초와 홀수초의 역할을 수행한다.

 

[정리된 코드]

# 16918 봄버맨
from collections import deque
from sys import stdin
input = stdin.readline
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

def bfs():
    while queue:
        y, x = queue.popleft()
        graph[y][x] = '.'
        for l in range(4):
            yy = dy[l] + y
            xx = dx[l] + x
            if 0 <= xx < c and 0 <= yy < r and graph[yy][xx] == 'O':
                graph[yy][xx] = '.'
                # queue.append((yy, xx)) 연쇄반응이 없다.

def search(): # 폭탄의 위치 큐에 추가
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'O':
                queue.append((i, j))

def bombSet(): # '.' -> 'O'으로 셋팅
    for i in range(r):
        for j in range(c):
            if graph[i][j] == '.':
                graph[i][j] = 'O'

r, c, n = map(int, input().split())
graph = []
for _ in range(r):
    graph.append(list(input().strip()))
n=n-1

while n:
    queue = deque()
    search()
    bombSet()
    n -= 1
    if n == 0:
        break
    bfs()
    n -= 1

for g in graph:
    print(*g, sep='')

• 위의 정리안 된 코드도 정답처리는 되었지만 다른 분의 블로그를 참고해서 정리된 코드를 올린다.