[백준 16918번] 파이썬 - 봄버맨

백준 16918_봄버맨

시간 제한 2초, 메모리 제한 512MB

조건

• 크기가 R×C인 직사각형 격자판 위에서 살고 있다.
• 격자의 각 칸은 비어있거나 폭탄이 들어있다.
  • 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다.
  • 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다.
  • 따라서, 연쇄 반응은 없다.
• 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다.
  • 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이 설치된 시간은 같다.
  • 다음 1초 동안 봄버맨은 아무것도 하지 않는다.
  • 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치한다. 즉, 모든 칸은 폭탄을 가지고 있게 된다. 폭탄은 모두 동시에 설치했다고 가정한다.
  • 1초가 지난 후에 3초 전에 설치된 폭탄이 모두 폭발한다.
  • 3과 4를 반복한다.

폭탄을 설치해놓은 초기 상태가 주어졌을 때, N초가 흐른 후의 격자판 상태를 구하려고 한다.

입력

• 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다.
• 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

접근 방법

• 문제 그대로 풀어주면 될 것 같다.\
  • 처음 1초는 아무일도 안하므로 -1
  • 이후 while문 돌리면서 단계 별로 함수를 실행해주는데
  • 함수를 실행한후 -1초를 해준다.

import sys  
from collections import deque  


# 1단계  
def loc_bomb():  
    for i in range(r):  
        for j in range(c):  
            if graph[i][j] == 'O':  
                bomb.append((i, j))  


# 3단계  
def full_bomb():  
    for i in range(r):  
        for j in range(c):  
            if graph[i][j] != "O":  
                graph[i][j] = "O"  


# 4단계  
def bombs():  
    dx = [-1, 1, 0, 0]  
    dy = [0, 0, -1, 1]  
    while bomb:  
        a, b = bomb.popleft()  
        graph[a][b] = "."  

        for i in range(4):  
            x = a + dx[i]  
            y = b + dy[i]  

            if 0 <= x < r and 0 <= y < c:  
                if graph[x][y] == "O":  
                    graph[x][y] = "."  


r, c, n = map(int, sys.stdin.readline().split())  
# 1단계: 폭탄을 설치  
graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(r)]  

# 2단계: 봄버맨은 아무것도 하지 않는다.  
n -= 1  

while n:  
    # 폭탄의 위치를 저장할 리스트  
    bomb = deque()  

    # 폭탄의 위치 저장  
    loc_bomb()  

    # 3단계: 모든 칸의 폭탄을 설치  
    full_bomb()  

    n -= 1  
    if n == 0:  
        break  

    # 4단계: 3초전에 설치된 폭탄 폭발  
    bombs()  
    n -= 1  

for i in graph:  
    print("".join(i))