봄버맨 (백준 16918번)

문제

봄버맨은 크기가 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‘로 주어진다.

출력

총 R개의 줄에 N초가 지난 후의 격자판 상태를 출력한다.

나의 풀이

import sys
import copy
input=sys.stdin.readline
R,C,N=map(int,input().strip().split())
maps=[]
bomb_list=[]
for i in range(R):
    m=list(input().strip())
    for j in range(C):
        if m[j]=='O':
            bomb_list.append([i,j])
    maps.append(m)

time=1
all_b_maps=[['O']*C for _ in range(R)]
answer=maps

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

while time<N:
    time+=1
    if time%2==0:
        answer=all_b_maps
    else:
        tmp=copy.deepcopy(all_b_maps)
        for b in bomb_list:
            tmp[b[0]][b[1]]='.'
            for i in range(4):
                bx=b[0]+dx[i]
                by=b[1]+dy[i]
                if 0<=bx<R and 0<=by<C:
                    tmp[bx][by]='.'
        bomb_list=[]
        answer=tmp
        for i in range(R):
            for j in range(C):
                if tmp[i][j]=='O':
                    bomb_list.append([i,j])
for i in range(R):
    print(''.join(answer[i]))

• 짝수 초에 폭탄이 모두 채워지고, 홀수 초에 폭탄이 터진다. 홀수 초에 터진 후의 폭탄의 list를 저장해놓고 다음 홀수 초에 사용한다.
• copy.deepcopy를 잘 기억해두자